oj.uz

Submission #65546

# Submission time Handle Problem Language Result Execution time Memory
65546 2018-08-08T00:24:59 Z KieranHorgan Pairs (IOI07_pairs) C++17
30 / 100
 2037 ms 525312 KB 
#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);
  }
};

struct FenwickTree {
  vector<vector<ll>> f;
  int N;
  FenwickTree(int N_) {
    f.assign(N_+1, vector<ll>(N_+1, 0));
    N=N_;
  }
  void add(int x, int y) {
    x++;
    y++;
    int Y = y;
    while(x <= N) {
      y = Y;
      while(y <= N) {
        f[x][y]++;
        y += y&-y;
      }
      x += x&-x;
    }
  }
  int get(int x, int y) {
    ll res = 0;
    x++;
    y++;
    int Y = y;
    while(x > 0) {
      y = Y;
      while(y > 0) {
        res += f[x][y];
        y -= y&-y;
      }
      x -= x&-x;
    }
    return res;
  }
  int query(int r1, int c1, int r2, int c2) {
    r1--; c1--;
    r2 = min(r2, N-1); c2 = min(c2, N-1);
    return get(r2, c2) - get(r1, c2) - get(r2, c1) + get(c1, r1);
  }
};

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);
    for(int i = 0; i < N; i++) {
      int x, y;
      cin >> x >> y;
      x--; y--;
      a[i] = {x+y, M-1-(x-y)};
    }

    FenwickTree ft(2*M+1);

    for(auto p: a) {
      int x = p.first;
      int y = p.second;
      ft.add(x, y);
    }

    for(auto p: a) {
      int x = p.first;
      int y = p.second;
      ans += ft.query(x-(D), y-(D), x+(D), y+(D));
      ans--;
    }

    // if(ans%2) return -1;
    cout << (ans)/2 << endl;
  }

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

    vector<FenwickTree> ft(M, FenwickTree(2*M+1));

    for(auto p: a) {
      int x = p.first.first;
      int y = p.first.second;
      int z = p.second;
      ft[z].add(x, y);
    }

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

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 544 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 876 KB Output is correct
2 Correct 26 ms 920 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 920 KB Output is correct
2 Correct 32 ms 1048 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1048 KB Output is correct
2 Correct 32 ms 1048 KB Output is correct
3 Correct 30 ms 1048 KB Output is correct

Subtask #6
0 / 7.0

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

Subtask #7
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 525312 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 154 ms 525312 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 525312 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 525312 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 511 ms 525312 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2037 ms 525312 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -