oj.uz

Submission #65540

# Submission time Handle Problem Language Result Execution time Memory
65540 2018-08-07T22:55:58 Z KieranHorgan Pairs (IOI07_pairs) C++17
70 / 100
 4000 ms 525312 KB 
#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;
 
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());
 
    int ans = 0;
    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);
    int ans = 0;
    for(auto p: a) {
      ans += st.query(p.first-D, p.second-D, p.first+D+1, p.second+D)-1;
      int cur = 0;
      for(auto q: a)
        if(q != p && max(abs(p.first-q.first), abs(p.second-q.second)) <= D) {
          cur++;
        }
    }
    // if(ans%2) return -1;
    cout << (ans)/2 << endl;
  }
 
  if(B == 3) {
    if(N <= 1000) M = 1;
    vector<vector<vector<vector<int>>>> grid(M*3, vector<vector<vector<int>>>(M*3, vector<vector<int>>(M*3, vector<int>(M*3, 0))));
    int X = 1, Y = 1, Z = 1, W=1;
    vector<pair<pair<int, int>, pair<int, int>>> a(N);
    vector<pair<int, pair<int, int>>> b(N);
    for(int i = 0; i < N; i++) {
      int x, y, z;
      cin >> x >> y >> z;
      b[i] = {x, {y, z}};
      // x=X,y=Y;z=Z; Z++; if(Z > M) Z=1,Y++; if(Y>M) Y=1,X++;
      x--; y--; z--;
      X = x+y+z;
      Y = M+x+y-z;
      Z = M+x-y+z;
      W = M-x+y+z;
      a[i] = {{X+1, Y+1}, {Z+1, W+1}};
      if(N > 100000)
        grid[X+1][Y+1][Z+1][W+1]++;
    }
    if(N <= 100000) {
      int ans = 0;
      for(auto p: b)
        for(auto q: b)
          if(abs((p.first-q.first))+abs((p.second.first-q.second.first))+abs((p.second.second-q.second.second)) <= D)
            ans++;
      ans -= N;
      cout << ans/2 << endl;
      return 0;
    }
 
    for(int x = 1; x < M*3; x++) {
      for(int y = 1; y < M*3; y++) {
        for(int z = 1; z < M*3; z++) {
          for(int w = 1; w < M*3; w++) {
            grid[x][y][z][w] += grid[x-1][y][z][w];
            grid[x][y][z][w] += grid[x][y-1][z][w];
            grid[x][y][z][w] += grid[x][y][z-1][w];
            grid[x][y][z][w] += grid[x][y][z][w-1];
 
            grid[x][y][z][w] -= grid[x-1][y-1][z][w];
            grid[x][y][z][w] -= grid[x][y-1][z-1][w];
            grid[x][y][z][w] -= grid[x-1][y][z-1][w];
            grid[x][y][z][w] -= grid[x-1][y][z][w-1];
            grid[x][y][z][w] -= grid[x][y-1][z][w-1];
            grid[x][y][z][w] -= grid[x][y][z-1][w-1];
 
            grid[x][y][z][w] += grid[x][y-1][z-1][w-1];
            grid[x][y][z][w] += grid[x-1][y][z-1][w-1];
            grid[x][y][z][w] += grid[x-1][y-1][z][w-1];
            grid[x][y][z][w] += grid[x-1][y-1][z-1][w];
 
            grid[x][y][z][w] -= grid[x-1][y-1][z-1][w-1];
          }
        }
      }
    }
 
    int ans = 0;
    for(auto p: a) {
      int x, y, z, w;
      x = p.first.first; y = p.first.second; z = p.second.first; w = p.second.second;
 
      int x1 = max(0ll, x-D-1);
      int y1 = max(0ll, y-D-1);
      int z1 = max(0ll, z-D-1);
      int w1 = max(0ll, w-D-1);
 
      int x2 = min(M*3-1, x+D);
      int y2 = min(M*3-1, y+D);
      int z2 = min(M*3-1, z+D);
      int w2 = min(M*3-1, w+D);
 
      int ansSt = ans;
 
      ans += grid[x2][y2][z2][w2];
 
      ans -= grid[x1][y2][z2][w2];
      ans -= grid[x2][y1][z2][w2];
      ans -= grid[x2][y2][z1][w2];
      ans -= grid[x2][y2][z2][w1];
 
      ans += grid[x1][y1][z2][w2];
      ans += grid[x2][y1][z1][w2];
      ans += grid[x1][y2][z1][w2];
      ans += grid[x2][y1][z2][w1];
      ans += grid[x1][y2][z2][w1];
      ans += grid[x2][y2][z1][w1];
 
      ans -= grid[x2][y1][z1][w1];
      ans -= grid[x1][y2][z1][w1];
      ans -= grid[x1][y1][z2][w1];
      ans -= grid[x1][y1][z1][w2];
 
      ans += grid[x1][y1][z1][w1];
 
      ans -= 1;
    }
    // cerr << ans << endl;
    cout << ans/2 << endl;
  }
}

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 400 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1772 KB Output is correct
2 Correct 27 ms 2044 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2876 KB Output is correct
2 Correct 29 ms 3852 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4708 KB Output is correct
2 Correct 39 ms 5572 KB Output is correct
3 Correct 35 ms 6444 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23708 KB Output is correct
2 Correct 27 ms 23748 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 23748 KB Output is correct
2 Correct 45 ms 23748 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 23748 KB Output is correct
2 Correct 268 ms 23748 KB Output is correct
3 Correct 268 ms 24380 KB Output is correct
4 Correct 271 ms 24748 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 52744 KB Output is correct
2 Correct 577 ms 52880 KB Output is correct
3 Correct 230 ms 52880 KB Output is correct
4 Correct 266 ms 52880 KB Output is correct

Subtask #10
10.0 / 10.0

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

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4058 ms 52880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1012 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1263 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -