oj.uz

Submission #262780

# Submission time Handle Problem Language Result Execution time Memory
262780 2020-08-13T08:52:01 Z 반딧불(#5089) Pairs (IOI07_pairs) C++17
100 / 100
 3027 ms 105100 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Query{
    int x, y, t; /// t: 0 (start), 1 (mid), 2 (end)
    Query(){}
    Query(int x, int y, int t): x(x), y(y), t(t){}

    bool operator<(const Query &r)const{
        if(y != r.y) return y<r.y;
        return t<r.t;
    }
};

vector<ll> tree, lazy;
void propagate(int i, int l, int r){
    if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
    else tree[i] += lazy[i] * (r-l+1);
    lazy[i] = 0;
}

void addTree(int i, int l, int r, int s, int e, ll val){
    propagate(i, l, r);
    if(l==s && r==e){
        lazy[i] += val;
        propagate(i, l, r);
        return;
    }
    int m = (l+r)>>1;
    if(s<=m) addTree(i*2, l, m, s, min(m, e), val);
    if(m<e) addTree(i*2+1, m+1, r, max(s, m+1), e, val);
}
ll getTree(int i, int l, int r, int idx){
    propagate(i, l, r);
    if(l==r) return tree[i];
    int m = (l+r)>>1;
    if(idx<=m) return getTree(i*2, l, m, idx);
    return getTree(i*2+1, m+1, r, idx);
}


int b, n, d, m;
int x[100002], y[100002], z[100002];
ll ans;
vector<Query> vec;

vector<vector<vector<ll> > > treee;
void update(int X, int Y, int Z, ll val){
    X = min(X, 226), Y = min(Y, 226), Z = min(Z, 226);
    X = max(X, 1), Y = max(Y, 1), Z = max(Z, 1);
    vector<ll> xVec, yVec, zVec;
    while(X<=225){
        xVec.push_back(X);
        X += X&(-X);
    }
    while(Y<=225){
        yVec.push_back(Y);
        Y += Y&(-Y);
    }
    while(Z<=225){
        zVec.push_back(Z);
        Z += Z&(-Z);
    }
    for(auto &_x: xVec) for(auto &_y: yVec) for(auto &_z: zVec) treee[_x][_y][_z] += val;
}

void realUpdate(int X, int Y, int Z, ll val){
    update(X-d, Y-d, Z-d, val);
    update(X-d, Y-d, Z+d+1, -val);
    update(X-d, Y+d+1, Z-d, -val);
    update(X+d+1, Y-d, Z-d, -val);
    update(X+d+1, Y+d+1, Z-d, val);
    update(X+d+1, Y-d, Z+d+1, val);
    update(X-d, Y+d+1, Z+d+1, val);
    update(X+d+1, Y+d+1, Z+d+1, -val);
}

ll getTree(int X, int Y, int Z){
    vector<ll> xVec, yVec, zVec;
    while(X) xVec.push_back(X), X -= X&(-X);
    while(Y) yVec.push_back(Y), Y -= Y&(-Y);
    while(Z) zVec.push_back(Z), Z -= Z&(-Z);
    ll ret = 0;
    for(auto &_x: xVec) for(auto &_y: yVec) for(auto &_z: zVec){
        ret += treee[_x][_y][_z];
    }
    return ret;
}

int main(){
    scanf("%d %d %d %d", &b, &n, &d, &m);
    for(int i=1; i<=n; i++){
        if(b>=1) scanf("%d", &x[i]);
        if(b>=2) scanf("%d", &y[i]);
        if(b>=3) scanf("%d", &z[i]);
    }

    if(b == 1){
        sort(x+1, x+n+1);
        x[n+1] = 2e9;

        int pnt = 1;
        for(int i=1; i<=n; i++){
            while(x[pnt+1] - x[i] <= d) pnt++;
            ans += ll(pnt - i);
        }
        printf("%lld", ans);
        return 0;
    }
    if(b == 2){
        tree.resize(1200000);
        lazy.resize(1200000);
        for(int i=1; i<=n; i++){
            vec.push_back({x[i]+y[i], x[i]-y[i]-d, 0});
            vec.push_back({x[i]+y[i], x[i]-y[i], 1});
            vec.push_back({x[i]+y[i], x[i]-y[i]+d, 2});
        }
        sort(vec.begin(), vec.end());

        for(auto tmp: vec){
            if(tmp.t == 0) addTree(1, 1, 300000, max(1, tmp.x-d), min(300000, tmp.x+d), 1);
            else if(tmp.t == 2) addTree(1, 1, 300000, max(1, tmp.x-d), min(300000, tmp.x+d), -1);
            else ans += getTree(1, 1, 300000, tmp.x);
        }
        printf("%lld", (ans-n)/2);
        return 0;
    }

    treee.resize(230);
    for(auto &x: treee){
        x.resize(230);
        for(auto &y: x){
            y.resize(230);
        }
    }

    for(int i=1; i<=n; i++){
        vec.push_back({i, x[i]+y[i]+z[i]-d, 0});
        vec.push_back({i, x[i]+y[i]+z[i], 1});
        vec.push_back({i, x[i]+y[i]+z[i]+d, 2});
    }

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

    for(auto &tmp: vec){
        int i = tmp.x, t = tmp.t;
        if(t == 0) realUpdate(x[i]+y[i]-z[i]+76, x[i]-y[i]+z[i]+76, x[i]-y[i]-z[i]+152, 1);
        if(t == 2) realUpdate(x[i]+y[i]-z[i]+76, x[i]-y[i]+z[i]+76, x[i]-y[i]-z[i]+152, -1);
        if(t == 1) ans += getTree(x[i]+y[i]-z[i]+76, x[i]-y[i]+z[i]+76, x[i]-y[i]-z[i]+152);
    }
    printf("%lld", (ans-n)/2);
}

Compilation message

pairs.cpp: In function 'int main()':
pairs.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |     scanf("%d %d %d %d", &b, &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:96:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |         if(b>=1) scanf("%d", &x[i]);
      |                  ~~~~~^~~~~~~~~~~~~
pairs.cpp:97:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |         if(b>=2) scanf("%d", &y[i]);
      |                  ~~~~~^~~~~~~~~~~~~
pairs.cpp:98:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |         if(b>=3) scanf("%d", &z[i]);
      |                  ~~~~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1024 KB Output is correct
2 Correct 26 ms 1144 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1608 KB Output is correct
2 Correct 26 ms 1528 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1616 KB Output is correct
2 Correct 33 ms 1656 KB Output is correct
3 Correct 23 ms 1536 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19200 KB Output is correct
2 Correct 15 ms 19200 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 26476 KB Output is correct
2 Correct 121 ms 26704 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 26984 KB Output is correct
2 Correct 146 ms 26984 KB Output is correct
3 Correct 158 ms 26984 KB Output is correct
4 Correct 150 ms 26960 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 27368 KB Output is correct
2 Correct 242 ms 27368 KB Output is correct
3 Correct 176 ms 27368 KB Output is correct
4 Correct 178 ms 27240 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 97784 KB Output is correct
2 Correct 92 ms 97784 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2149 ms 105064 KB Output is correct
2 Correct 2193 ms 105100 KB Output is correct
3 Correct 1686 ms 105064 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2284 ms 105064 KB Output is correct
2 Correct 3027 ms 105064 KB Output is correct
3 Correct 1749 ms 105064 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2594 ms 105064 KB Output is correct
2 Correct 2728 ms 105064 KB Output is correct
3 Correct 1778 ms 105064 KB Output is correct