Submission #126140

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
126140	2019-07-07T05:53:58 Z	nvmdava	Pairs (IOI07_pairs)	C++17	100 / 100	216 ms	16192 KB

pairs

#include <bits/stdc++.h>
using namespace std;

int a[100005];

void solve1(){
   int n, d, m;
   cin>>n>>d>>m;
   for(int i = 1; i <= n; i++)
      cin>>a[i];
   sort(a + 1, a + n + 1);
   long long res = 0;
   for(int i = 1; i <= n; i++){
      res += (i - (lower_bound(a + 1, a + n + 1, a[i] - d) - (a)));
   }
   cout<<res;
}

int t[500000];
int L, R;

void update(int id, int l, int r){
   if(l > L || r < L) return;
   t[id] += R;
   if(l == r) return;
   int m = (l + r) >> 1;
   update(id << 1, l, m);
   update(id << 1 | 1, m + 1, r);
}
int query(int id, int l, int r){
   if(l > R || r < L) return 0;
   if(l >= L && r <= R) return t[id];
   int m = (l + r) >> 1;
   return query(id << 1, l, m) + query(id << 1 | 1, m + 1, r);
}
vector<int> lol[200000];

void solve2(){
   int n, d, m;
   cin>>n>>d>>m;
   for(int i = 1; i <= n; i++){
      int x, y;
      cin>>x>>y;
      lol[x + y].push_back(x - y + m);
   }
   m <<= 1;
   long long res = 0;
   for(int i = 1; i <= m; i++){
      for(int& x : lol[i]){
         L = max(x - d, 1);
         R = min(x + d, m);
         res += query(1, 1, m);
         L = x; R = 1;
         update(1, 1, m);
      }
      if(i >= d){
         for(int& x : lol[i - d]){
            L = x; R = -1;
            update(1, 1, m);
         }
      }
   }
   cout<<res;
}
int x[100005], y[100005], z[100005];

int pref[80][200][200];
int n, d, m;
int sum(int lev, int L, int R, int D, int U){
   L = max(L, 1) - 1;
   R = min(R, 2 * m);
   D = max(D, 1) - 1;
   U = min(U, 2 * m);
   return pref[lev][R][U] - pref[lev][L][U] - pref[lev][R][D] + pref[lev][L][D];
}

void solve3(){
   cin>>n>>d>>m;
   for(int i = 1; i <= n; i++){
      cin>>x[i]>>y[i]>>z[i];
      pref[x[i]][y[i] + z[i]][y[i] - z[i] + m]++;
   }
   for(int i = 1; i <= m; i++)
      for(int j = 1; j <= 2 * m; j++)
         for(int k = 1; k <= 2 * m; k++)
            pref[i][j][k] += pref[i][j - 1][k] + pref[i][j][k - 1] - pref[i][j - 1][k - 1];
   long long res = 0;
   for(int i = 1; i <= n; i++){
      res += sum(x[i], y[i] + z[i] - d, y[i] + z[i] + d, y[i] - z[i] + m - d, y[i] - z[i] + m + d) - 1;
      for(int j = min(d, m); j > 0; j--){
         int nd = d - j;
         if(x[i] - j >= 0)
            res += sum(x[i] - j, y[i] + z[i] - nd, y[i] + z[i] + nd, y[i] - z[i] + m - nd, y[i] - z[i] + m + nd);
         if(x[i] + j <= m)
            res += sum(x[i] + j, y[i] + z[i] - nd, y[i] + z[i] + nd, y[i] - z[i] + m - nd, y[i] - z[i] + m + nd);
      }
   }
   cout<<res / 2;
}
int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   int test;
   cin>>test;
   if(test == 1) solve1();
   if(test == 2) solve2();
   if(test == 3) solve3();
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	6 ms	5112 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	5112 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	5412 KB	Output is correct
2	Correct	23 ms	5368 KB	Output is correct

Subtask #4
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	5480 KB	Output is correct
2	Correct	31 ms	5388 KB	Output is correct

Subtask #5
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	5496 KB	Output is correct
2	Correct	32 ms	5468 KB	Output is correct
3	Correct	30 ms	5368 KB	Output is correct

Subtask #6
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	6648 KB	Output is correct
2	Correct	9 ms	6648 KB	Output is correct

Subtask #7
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	5624 KB	Output is correct
2	Correct	31 ms	5556 KB	Output is correct

Subtask #8
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	5812 KB	Output is correct
2	Correct	61 ms	5752 KB	Output is correct
3	Correct	62 ms	5752 KB	Output is correct
4	Correct	58 ms	5780 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	128 ms	9208 KB	Output is correct
2	Correct	118 ms	9208 KB	Output is correct
3	Correct	78 ms	7692 KB	Output is correct
4	Correct	77 ms	7552 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	14200 KB	Output is correct
2	Correct	21 ms	14200 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	6392 KB	Output is correct
2	Correct	36 ms	6392 KB	Output is correct
3	Correct	36 ms	6392 KB	Output is correct

Subtask #12
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	74 ms	12116 KB	Output is correct
2	Correct	141 ms	12124 KB	Output is correct
3	Correct	93 ms	12996 KB	Output is correct

Subtask #13
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	154 ms	15228 KB	Output is correct
2	Correct	216 ms	16192 KB	Output is correct
3	Correct	123 ms	16120 KB	Output is correct

Submission #126140

Compilation message