oj.uz

Submission #1089594

# Submission time Handle Problem Language Result Execution time Memory
1089594 2024-09-16T18:51:51 Z BLOBVISGOD Pairs (IOI07_pairs) C++17
100 / 100
 124 ms 10332 KB 
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

struct fentree{
    vi a;
    fentree(int n) : a(n+1) {}
    void add(int i, int v){
        for(i++; i<sz(a); i+= i&(-i)) a[i]+=v;
    }

    // [0,r)
    int get(int r){
        int ans = 0;
        for(;r>0; r-=r&(-r)) ans += a[r];
        return ans;
    }
};

void trans(int& x, int& y, int B){
    int nx = x+y;
    y = B+y-x;
    x = nx;
}

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int b,n,d,m; cin >> b >> n >> d >> m;
    ll ans = 0;
    if (b==1){
        vi a(n);
        rep(i,0,n) cin >> a[i];
        sort(all(a)); 
        for(auto c : a){
            int lo = lower_bound(all(a),c-d)-begin(a);
            int hi = upper_bound(all(a),c+d)-begin(a); hi--;
            // one element is c itself, so closed interval counts;
            ans += max(0,hi-lo);
        }
    }else if (b==2){
        int B = 75005;

        struct event{
            // type 1 = add/remove, type 0 = update
            int x, y, mul, type;
            bool operator<(event b){
                return x<b.x or (x==b.x and type < b.type);
            }
        };
        int at = 0;
        vector<event> E(n*5);
        ans -= n;

        while(n--){
            int x,y; cin >> x >> y;
            trans(x,y,B);
            E[at++] = {x,y,1,0};
            E[at++] = {x+d,min(B*2,y+d+1),1,1}; // assume halfopen queries in fentree, closed in events
            E[at++] = {x-d-1,min(B*2,y+d+1),-1,1};
            E[at++] = {x+d,max(0,y-d),-1,1};
            E[at++] = {x-d-1,max(0,y-d),1,1};
        }

        fentree fen(B*2+1);

        sort(all(E));
        for(auto e : E){
            if (e.type==0){
                fen.add(e.y,e.mul);
            }else{
                ans += e.mul*fen.get(e.y);
            }
        }
    }else{
        int B = 77;
        vector<vector<vector<int>>> a(B+1,vvi(B*2+1,vi(B*2+1)));
        vector<array<int,3>> qs(n);
        rep(i,0,n) rep(j,0,3) cin >> qs[i][j];

        for(auto [x,y,z] : qs){
            trans(y,z,B);
            a[x][y][z]++;
        }

        rep(i,0,sz(a)) rep(j,0,sz(a[0])) rep(k,0,sz(a[0])-1) a[i][j][k+1] += a[i][j][k];
        rep(i,0,sz(a)) rep(j,0,sz(a[0])-1) rep(k,0,sz(a[0])) a[i][j+1][k] += a[i][j][k];

        auto get = [&](int x,int y, int z) -> int {
            x = max(0,min(x,B));
            y = max(0,min(y,B*2));
            z = max(0,min(z,B*2));
            return a[x][y][z];
        };

        for (auto [x,y,z] : qs){
            trans(y,z,B);
            rep(i,0,B){
                int nd = d-abs(x-i);
                if (nd<0) continue;
                ans += get(i,y+nd,z+nd) - get(i,y-nd-1,z+nd) - get(i,y+nd,z-nd-1) + get(i,y-nd-1,z-nd-1);
            }
            ans --;
        }
    }

    cout << ans/2 << '\n';
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1116 KB Output is correct
2 Correct 11 ms 1116 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1484 KB Output is correct
2 Correct 15 ms 1628 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1628 KB Output is correct
2 Correct 16 ms 1628 KB Output is correct
3 Correct 19 ms 1628 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1056 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 9308 KB Output is correct
2 Correct 40 ms 9308 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9564 KB Output is correct
2 Correct 48 ms 9560 KB Output is correct
3 Correct 48 ms 9560 KB Output is correct
4 Correct 47 ms 9616 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10008 KB Output is correct
2 Correct 58 ms 10004 KB Output is correct
3 Correct 51 ms 9820 KB Output is correct
4 Correct 57 ms 9820 KB Output is correct

Subtask #10
10.0 / 10.0

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

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10076 KB Output is correct
2 Correct 38 ms 10076 KB Output is correct
3 Correct 51 ms 10096 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 10332 KB Output is correct
2 Correct 122 ms 10328 KB Output is correct
3 Correct 61 ms 10332 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 10328 KB Output is correct
2 Correct 124 ms 10228 KB Output is correct
3 Correct 61 ms 10192 KB Output is correct