oj.uz

Submission #126134

# Submission time Handle Problem Language Result Execution time Memory
126134 2019-07-07T05:44:34 Z nvmdava Pairs (IOI07_pairs) C++17
70 / 100
 200 ms 15352 KB 
#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 <= 2 * 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 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5452 KB Output is correct
2 Correct 23 ms 5476 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 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 45 ms 5604 KB Output is correct
2 Correct 35 ms 5624 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 9176 KB Output is correct
2 Correct 117 ms 9188 KB Output is correct
3 Correct 77 ms 7612 KB Output is correct
4 Correct 76 ms 7544 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 14200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6520 KB Output is correct
2 Correct 39 ms 6396 KB Output is correct
3 Correct 42 ms 6496 KB Output is correct

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 12024 KB Output is correct
2 Incorrect 200 ms 12136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 15352 KB Output isn't correct
2 Halted 0 ms 0 KB -