Submission #65710

#	Time	Username	Problem	Language	Result	Execution time	Memory
65710		KieranHorgan	Pairs (IOI07_pairs)	C++17	100 / 100	568 ms	34164 KiB

pairs

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define ll long long
// #define int long long
#define ld double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)

int B, N, D, M;
int n;
ll ans;

vector<vector<int>> rows;
struct SegmentTree {
  vector<vector<int>> st;
  SegmentTree(int N_) {
    n = N_;
    st.assign(4*n, vector<int>(0));
    build();
  }
  void build(int id=1, int l=0, int r=n) {
    if(l+1 == r) {
      st[id] = rows[l];
      return;
    }

    int mid = (l+r)/2;
    build(id*2  , l, mid);
    build(id*2+1, mid, r);
    merge(st[id*2].begin(), st[id*2].end(), st[id*2+1].begin(), st[id*2+1].end(), back_inserter(st[id]));
  }

  int query(int r1, int c1, int r2, int c2, int id=1, int l=0, int r=n) {
    if(l >= r1 && r <= r2) {
      return upper_bound(st[id].begin(), st[id].end(), c2)-lower_bound(st[id].begin(), st[id].end(), c1);
    }
    if(l >= r2 || r <= r1) return 0;

    int mid = (l+r)/2;
    return query(r1, c1, r2, c2, id*2  , l, mid) + query(r1, c1, r2, c2, id*2+1, mid, r);
  }
};

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> B >> N >> D >> M;

  if(B == 1) {
    vector<int> a(N);
    for(auto &x: a)
      cin >> x;

    sort(a.begin(), a.end());

    for(auto x: a)
      ans += upper_bound(a.begin(), a.end(), x+D)-lower_bound(a.begin(), a.end(), x-D)-1;

    cout << ans/2 << endl;
  }

  if(B == 2) {
    vector<pair<int, int>> a(N);
    rows.assign(2*M-1, vector<int>(0));
    for(int i = 0; i < N; i++) {
      int x, y;
      cin >> x >> y;
      x--; y--;
      rows[x+y].push_back(M-1-(x-y));
      a[i] = {x+y, M-1-(x-y)};
    }
 
    for(auto &v: rows)
      sort(v.begin(), v.end());
 
    SegmentTree st(2*M-1);
    for(auto p: a) {
      ans += st.query(p.first-D, p.second-D, p.first+D+1, p.second+D)-1;
    }
    // if(ans%2) return -1;
    cout << (ans)/2 << endl;
  }

  if(B == 3) {
    vector<pair<pair<int, int>, int>> a(N);
    vector<vector<vector<int>>> grid(M+1, vector<vector<int>>(M*2+2, vector<int>(M*2+2)));
    for(int i = 0; i < N; i++) {
      int x, y, z;
      cin >> x >> y >> z;
      a[i] = {{x+y, M-(x-y)+1}, z};
      grid[z][x+y][M-(x-y)+1]++;
    }

    for(int z = 1; z <= M; z++)
      for(int x = 1; x <= 2*M+1; x++)
        for(int y = 1; y <= 2*M+1; y++)
          grid[z][x][y] += grid[z][x-1][y] + grid[z][x][y-1] - grid[z][x-1][y-1];

    for(auto p: a) {
      int x = p.first.first;
      int y = p.first.second;
      int z = p.second;
      int ansSt = ans;
      // cout << x << " " << y << " " << z << ": ";
      for(int Z = max(0, z-D); Z <= min(M, z+D); Z++) {
        // cerr << Z << ":" << y-(D-abs(Z-z)) << ":" << y+(D-abs(Z-z)) << " ";
        // cerr << Z << endl;
        ans += grid[Z][min(2*M+1, x+(D-abs(Z-z)))][min(2*M+1, y+(D-abs(Z-z)))] - grid[Z][min(2*M+1, x+(D-abs(Z-z)))][max(0, -1+y-(D-abs(Z-z)))] - grid[Z][max(0, -1+x-(D-abs(Z-z)))][min(2*M+1, y+(D-abs(Z-z)))] + grid[Z][max(0, -1+x-(D-abs(Z-z)))][max(0, -1+y-(D-abs(Z-z)))];
      }
      ans--;
      // cerr << ans-ansSt << endl;
    }
    // if(ans%2) return -1;
    cout << (ans)/2 << endl;
  }
}

Compilation message (stderr)

pairs.cpp: In function 'int main()':
pairs.cpp:108:11: warning: unused variable 'ansSt' [-Wunused-variable]
       int ansSt = ans;
           ^~~~~

• 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