oj.uz

Submission #160630

# Submission time Handle Problem Language Result Execution time Memory
160630 2019-10-29T02:09:45 Z dantoh000 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 13408 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
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);
        }
    }
    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, int k){
        //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,k);
            r->spray(m+1,y,k);
            v = l->v + r-> v;
        }
        else{
            if (x > m) r -> spray(x,y,k);
            else if (y <= m) l -> spray(x,y,k);
            else l -> spray(x,m,k), r -> spray(m+1,y,k);
            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,k;
    scanf("%lld%lld%lld",&n,&q,&k);
    root = new node (0,n-1);
    for (int i = 0; i < n; i++){
        int x;
        scanf("%lld",&x);
        root -> up(i,x);
    }
    for (int i = 0; i < q; i++){
        int qu,a,b;
        scanf("%lld%lld%lld",&qu,&a,&b);
        if (qu == 1){
            root -> up(--a,b);
        }
        else if (qu == 2){
            root -> spray(--a,--b,k);
        }
        else if (qu == 3){
            printf("%lld\n",root->sum(--a,--b));
        }
        //for (int i = 0; i < n; i++){
        //    printf("%lld ",root->sum(i,i));
        //}
        //printf("\n");
    }


}

Compilation message

sterilizing.cpp:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:48: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:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&x);
         ~~~~~^~~~~~~~~~~
sterilizing.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&qu,&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 7 ms 508 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 8 ms 760 KB Output is correct
7 Correct 7 ms 632 KB Output is correct
8 Correct 21 ms 636 KB Output is correct
9 Correct 8 ms 764 KB Output is correct
10 Correct 7 ms 732 KB Output is correct
11 Correct 7 ms 632 KB Output is correct
12 Correct 7 ms 760 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1144 KB Output is correct
2 Correct 34 ms 5880 KB Output is correct
3 Correct 44 ms 6008 KB Output is correct
4 Correct 94 ms 3452 KB Output is correct
5 Correct 162 ms 12956 KB Output is correct
6 Correct 161 ms 12936 KB Output is correct
7 Execution timed out 5019 ms 13176 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 7032 KB Output is correct
2 Correct 171 ms 7160 KB Output is correct
3 Correct 205 ms 6136 KB Output is correct
4 Correct 203 ms 4740 KB Output is correct
5 Correct 280 ms 13140 KB Output is correct
6 Correct 299 ms 13184 KB Output is correct
7 Correct 292 ms 13100 KB Output is correct
8 Correct 462 ms 13152 KB Output is correct
9 Correct 259 ms 13408 KB Output is correct
10 Correct 303 ms 13176 KB Output is correct
11 Correct 349 ms 13176 KB Output is correct
12 Correct 378 ms 13304 KB Output is correct