oj.uz

Submission #160634

# Submission time Handle Problem Language Result Execution time Memory
160634 2019-10-29T03:00:43 Z dantoh000 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 390 ms 16676 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){
        if (k == 1) return;
        //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:54:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:58:13: warning: unused variable 'x' [-Wunused-variable]
         int x;
             ^
sterilizing.cpp:56: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:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&c[i]);
         ~~~~~^~~~~~~~~~~~~~
sterilizing.cpp:64: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 7 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 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 7 ms 760 KB Output is correct
12 Correct 7 ms 764 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 7696 KB Output is correct
2 Correct 74 ms 6792 KB Output is correct
3 Correct 85 ms 12588 KB Output is correct
4 Correct 108 ms 15992 KB Output is correct
5 Correct 132 ms 16504 KB Output is correct
6 Correct 125 ms 16536 KB Output is correct
7 Correct 130 ms 16676 KB Output is correct
8 Correct 123 ms 16632 KB Output is correct
9 Correct 106 ms 16416 KB Output is correct
10 Correct 103 ms 16452 KB Output is correct
11 Correct 105 ms 16376 KB Output is correct
12 Correct 103 ms 16376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1220 KB Output is correct
2 Correct 27 ms 6264 KB Output is correct
3 Correct 37 ms 6264 KB Output is correct
4 Correct 91 ms 3652 KB Output is correct
5 Correct 153 ms 13688 KB Output is correct
6 Correct 206 ms 13844 KB Output is correct
7 Correct 119 ms 14468 KB Output is correct
8 Correct 147 ms 15096 KB Output is correct
9 Correct 106 ms 14968 KB Output is correct
10 Correct 106 ms 14968 KB Output is correct
11 Correct 111 ms 15096 KB Output is correct
12 Correct 111 ms 14972 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 7380 KB Output is correct
2 Correct 161 ms 7516 KB Output is correct
3 Correct 186 ms 6504 KB Output is correct
4 Correct 200 ms 4892 KB Output is correct
5 Correct 253 ms 13944 KB Output is correct
6 Correct 281 ms 13944 KB Output is correct
7 Correct 256 ms 13944 KB Output is correct
8 Correct 339 ms 13988 KB Output is correct
9 Correct 250 ms 13944 KB Output is correct
10 Correct 390 ms 14092 KB Output is correct
11 Correct 215 ms 13948 KB Output is correct
12 Correct 377 ms 13976 KB Output is correct