oj.uz

Submission #262768

# Submission time Handle Problem Language Result Execution time Memory
262768 2020-08-13T08:36:36 Z 반딧불(#5089) Training (IOI07_training) C++17
0 / 100
 50 ms 27384 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

training.cpp: In function 'int main()':
training.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);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
training.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]);
      |                  ~~~~~^~~~~~~~~~~~~
training.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]);
      |                  ~~~~~^~~~~~~~~~~~~
training.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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 13056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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