Submission #126140

#	Time	Username	Problem	Language	Result	Execution time	Memory
126140		nvmdava	Pairs (IOI07_pairs)	C++17	100 / 100	216 ms	16192 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;
}
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 / 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: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10