Submission #126114

#	Time	Username	Problem	Language	Result	Execution time	Memory
126114		nvmdava	Pairs (IOI07_pairs)	C++17	60 / 100	120 ms	10360 KiB

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;
}


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 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10