fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  4. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  5. #define ll long long
  6.  
  7. using namespace std;
  8.  
  9. const int N = 1e6 + 5;
  10. const int mod = 1e9 + 7;
  11. int type, c, n, x[N], d[N];
  12. ll a[N];
  13.  
  14. void nhap() {
  15.     cin >> type >> n >> c;
  16.     FOR(i, 1, n) cin >> x[i] >> d[i];
  17. }
  18.  
  19. namespace sub1 {
  20.     bool check() {
  21.         return type == 1 && n <= 1000;
  22.     }
  23.  
  24.     bool ok(int u, int v) {
  25.         int len = x[v] - x[u];
  26.         return (len * c == d[u] + d[v]);
  27.     }
  28.  
  29.     void solve() {
  30.         int ans = 0;
  31.         FOR(i, 1, n) FOR(j, i + 1, n) if (ok(i, j)) ++ans;
  32.         cout << ans;
  33.     }
  34. }
  35.  
  36. namespace sub2 {
  37.     bool check() {
  38.         return type == 1 && n <= 2e5;
  39.     }
  40.  
  41.     void solve() {
  42.         map <int, int> cnt;
  43.         int ans = 0;
  44.         FOR(i, 1, n) {
  45.             int key = d[i] - c * x[i];
  46.             ans = (ans + cnt[-key]) % mod;
  47.             ++cnt[d[i] + c * x[i]];
  48.         }
  49.         cout << ans;
  50.     }
  51. }
  52.  
  53. ll pw(ll a, ll b) {
  54.     ll res = 1;
  55.     while (b) {
  56.         if (b & 1) res = res * a % mod;
  57.         a = a * a % mod;
  58.         b >>= 1;
  59.     }
  60.     return res;
  61. }
  62.  
  63. namespace sub4 {
  64.     ll pow2[N];
  65.     bool check() {
  66.         return type == 2 && n <= 1000;
  67.     }
  68.  
  69.     bool ok(int u, int v) {
  70.         int len = x[v] - x[u];
  71.         return (len * c == d[u] + d[v]);
  72.     }
  73.  
  74.     void solve() {
  75.         int ans = 0;
  76.         pow2[0] = 1;
  77.         FOR(i, 1, n) pow2[i] = (pow2[i - 1] * 2) % mod;
  78.         FOR(i, 1, n) FOR(j, i + 1, n) if (ok(i, j)) {
  79.             ans = (ans + pow2[j - i - 1]) % mod;
  80.         }
  81.         cout << ans;
  82.     }
  83. }
  84.  
  85. namespace sub5 {
  86.     ll pow2[N], inv[N];
  87.     bool check() {
  88.         return type == 2;
  89.     }
  90.  
  91.     void solve() {
  92.         map <ll, int> sum;
  93.         int ans = 0;
  94.  
  95.         FOR(i, 1, n) a[i] =  x[i] * c;
  96.         pow2[0] = 1;
  97.         FOR(i, 1, n) pow2[i] = (pow2[i - 1] * 2) % mod;
  98.         inv[0] = 1;
  99.         FOR(i, 1, n + 1) inv[i] = inv[i - 1] * 500000004 % mod;
  100.  
  101.         FOR(i, 1, n) {
  102.             ans = (ans + pow2[i] * sum[a[i] - d[i]]) % mod;
  103.             sum[a[i] + d[i]] = (sum[a[i] + d[i]] + inv[i + 1]) % mod;
  104.         }
  105.  
  106.         cout << ans;
  107.     }
  108. }
  109.  
  110. void giai() {
  111.     if (sub2::check()) sub2::solve();
  112.     else if (sub5::check()) sub5::solve();
  113. }
  114.  
  115. int main() {
  116.     ios_base::sync_with_stdio(0);
  117.     cin.tie(0); cout.tie(0);
  118.  
  119.     #define name "test"
  120.  
  121.     if (fopen(name".inp", "r")) {
  122.         freopen(name".inp", "r", stdin);
  123.         freopen(name".out", "w", stdout);
  124.     }
  125.  
  126.     nhap();
  127.     giai();
  128.  
  129.     return 0;
  130. }
  131.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QpIsFF
language:
C++14 (clang 8.0)
created:
16 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!