oj.uz

Submission #126114

# Submission time Handle Problem Language Result Execution time Memory
126114 2019-07-07T05:18:55 Z nvmdava Pairs (IOI07_pairs) C++17
60 / 100
 120 ms 10360 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;
}


void solve3(){

}
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 5112 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5768 KB Output is correct
2 Correct 30 ms 5724 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5624 KB Output is correct
2 Correct 32 ms 5752 KB Output is correct
3 Correct 31 ms 5752 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 44 ms 6136 KB Output is correct
2 Correct 32 ms 6136 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 6520 KB Output is correct
2 Correct 62 ms 6520 KB Output is correct
3 Correct 61 ms 6392 KB Output is correct
4 Correct 59 ms 6512 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 10232 KB Output is correct
2 Correct 113 ms 10360 KB Output is correct
3 Correct 82 ms 8824 KB Output is correct
4 Correct 83 ms 8652 KB Output is correct

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 10.0

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