oj.uz

Submission #160632

# Submission time Handle Problem Language Result Execution time Memory
160632 2019-10-29T02:20:03 Z dantoh000 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 14072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int k;
int c[100005];
struct node {
    int s,e,m,v;
    node *l, *r;
    node (int _s, int _e){
        s = _s; e = _e; m = (s+e)/2;

        if (s != e){
            l = new node (s,m);
            r = new node (m+1,e);
            v = l->v + r->v;
        }
        else{
            v = c[s];
        }
    }
    void up(int x, int nv){
        if (s == e) {v = nv; return;}
        if (x > m) r -> up(x,nv);
        if (x <= m) l -> up(x,nv);
        v = l->v + r->v;
    }
    void spray(int x, int y){
        //printf("%lld %lld %lld %lld %lld\n",s,e,x,y,k);
        if (s == e){
            v /= k;
            return;
        }
        else if (s == x && e == y){
            if (v == 0) return;
            l->spray(x,m);
            r->spray(m+1,y);
            v = l->v + r-> v;
        }
        else{
            if (x > m) r -> spray(x,y);
            else if (y <= m) l -> spray(x,y);
            else l -> spray(x,m), r -> spray(m+1,y);
            v = l->v + r->v;
        }
    }
    int sum(int x, int y){
        if (s == x && e == y) return v;
        if (x > m) return r -> sum(x,y);
        if (y <= m) return l -> sum(x,y);
        return l->sum(x,m) + r->sum(m+1,y);
    }
} *root;
main(){
    int n,q;
    scanf("%lld%lld%lld",&n,&q,&k);
    for (int i = 0; i < n; i++){
        int x;
        scanf("%lld",&c[i]);
    }
    root = new node(0,n-1);
    for (int i = 0; i < q; i++){
        int s,t,u;
        scanf("%lld%lld%lld",&s,&t,&u);
        if (s == 1){
            root -> up(--t,u);
        }
        else if (s == 2){
            root -> spray(--t,--u);
        }
        else if (s == 3){
            printf("%lld\n",root->sum(--t,--u));
        }
        //for (int i = 0; i < n; i++){
        //    printf("%lld ",root->sum(i,i));
        //}
        //printf("\n");
    }


}

Compilation message

sterilizing.cpp:53:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:57:13: warning: unused variable 'x' [-Wunused-variable]
         int x;
             ^
sterilizing.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld",&n,&q,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&c[i]);
         ~~~~~^~~~~~~~~~~~~~
sterilizing.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&s,&t,&u);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 7 ms 504 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 7 ms 760 KB Output is correct
8 Correct 7 ms 760 KB Output is correct
9 Correct 8 ms 760 KB Output is correct
10 Correct 7 ms 760 KB Output is correct
11 Correct 9 ms 760 KB Output is correct
12 Correct 9 ms 760 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5078 ms 7396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1144 KB Output is correct
2 Correct 27 ms 6324 KB Output is correct
3 Correct 40 ms 6364 KB Output is correct
4 Correct 92 ms 3576 KB Output is correct
5 Correct 197 ms 13712 KB Output is correct
6 Correct 145 ms 13800 KB Output is correct
7 Execution timed out 5006 ms 13968 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 7416 KB Output is correct
2 Correct 158 ms 7420 KB Output is correct
3 Correct 183 ms 6416 KB Output is correct
4 Correct 191 ms 4984 KB Output is correct
5 Correct 267 ms 13912 KB Output is correct
6 Correct 291 ms 13944 KB Output is correct
7 Correct 237 ms 13944 KB Output is correct
8 Correct 357 ms 13944 KB Output is correct
9 Correct 248 ms 13944 KB Output is correct
10 Correct 285 ms 14072 KB Output is correct
11 Correct 210 ms 14072 KB Output is correct
12 Correct 372 ms 13960 KB Output is correct