oj.uz

Submission #262695

# Submission time Handle Problem Language Result Execution time Memory
262695 2020-08-13T07:12:34 Z 반딧불(#5089) Pairs (IOI07_pairs) C++17
46 / 100
 2214 ms 125548 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;
    }
};

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

ll tree[300][300][300];
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) tree[_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 += tree[_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]);
    }

    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:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%d %d %d %d", &b, &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:69:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |         if(b>=1) scanf("%d", &x[i]);
      |                  ~~~~~^~~~~~~~~~~~~
pairs.cpp:70:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |         if(b>=2) scanf("%d", &y[i]);
      |                  ~~~~~^~~~~~~~~~~~~
pairs.cpp:71:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |         if(b>=3) scanf("%d", &z[i]);
      |                  ~~~~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 6.0

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

Subtask #4
0 / 6.0

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

Subtask #5
0 / 6.0

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

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 640 KB Execution killed with signal 11 (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 561 ms 59992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 8.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 48504 KB Output is correct
2 Correct 17 ms 1952 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1641 ms 8424 KB Output is correct
2 Correct 1643 ms 10840 KB Output is correct
3 Correct 1328 ms 11476 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1761 ms 60732 KB Output is correct
2 Correct 2115 ms 112500 KB Output is correct
3 Correct 1284 ms 15064 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2105 ms 107692 KB Output is correct
2 Correct 2214 ms 125548 KB Output is correct
3 Correct 1297 ms 20952 KB Output is correct