oj.uz

Submission #77980

# Submission time Handle Problem Language Result Execution time Memory
77980 2018-10-01T14:53:21 Z nxteru Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 776 ms 72488 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
struct spr{
    ll x[30];
    spr(){
        for(int i=0;i<30;i++)x[i]=0;
    }
    spr operator +(spr &q){
        spr res;
        for(int i=0;i<30;i++)res.x[i]=x[i]+q.x[i];
        return res;
    }
    void st(int a){
        for(int i=0;i<30;i++){
            if(i+a<30)x[i]=x[i+a];
            else x[i]=0;
        }
    }
    void ch(ll a,ll k){
        x[0]=a;
        for(int i=1;i<30;i++)x[i]=x[i-1]/k;
    }
};
ll n,q,k,la[1<<18];
spr seg[1<<18];
void lazy(int l,int r,int o){
    if(la[o]==0)return;
    seg[o].st(la[o]);
    if(l!=r){
        la[o*2+1]+=la[o];
        la[o*2+2]+=la[o];
    }
    la[o]=0;
}
void up(int a,int b,int l,int r,int o,ll x){
    lazy(l,r,o);
    if(r<a||b<l)return;
    if(a<=l&&r<=b){
        seg[o].ch(x,k);
        return;
    }
    up(a,b,l,(l+r-1)/2,o*2+1,x);
    up(a,b,(l+r+1)/2,r,o*2+2,x);
    seg[o]=seg[o*2+1]+seg[o*2+2];
}
void cha(int a,int b,int l,int r,int o){
    lazy(l,r,o);
    if(r<a||b<l)return;
    if(a<=l&&r<=b){
        la[o]++;
        lazy(l,r,o);
        return;
    }
    cha(a,b,l,(l+r-1)/2,o*2+1);
    cha(a,b,(l+r+1)/2,r,o*2+2);
    seg[o]=seg[o*2+1]+seg[o*2+2];
}
ll sum(int a,int b,int l,int r,int o){
    lazy(l,r,o);
    if(r<a||b<l)return 0;
    if(a<=l&&r<=b)return seg[o].x[0];
    return sum(a,b,l,(l+r-1)/2,o*2+1)+sum(a,b,(l+r+1)/2,r,o*2+2);
}
int main(void){
    scanf("%lld%lld%lld",&n,&q,&k);
    for(int i=0;i<n;i++){
        ll a;
        scanf("%lld",&a);
        up(i,i,0,(1<<17)-1,0,a);
    }
    while(q){
        ll s,a,b;
        scanf("%lld%lld%lld",&s,&a,&b);
        if(s==1){
            up(a-1,a-1,0,(1<<17)-1,0,b);
        }
        if(s==2&&k!=1){
            cha(a-1,b-1,0,(1<<17)-1,0);
        }
        if(s==3){
            printf("%lld\n",sum(a-1,b-1,0,(1<<17)-1,0));
        }
        q--;
    }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:83: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:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a);
         ~~~~~^~~~~~~~~~~
sterilizing.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&s,&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 61944 KB Output is correct
2 Correct 53 ms 61944 KB Output is correct
3 Correct 55 ms 62032 KB Output is correct
4 Correct 59 ms 62220 KB Output is correct
5 Correct 64 ms 62540 KB Output is correct
6 Correct 65 ms 62604 KB Output is correct
7 Correct 66 ms 62604 KB Output is correct
8 Correct 70 ms 62660 KB Output is correct
9 Correct 65 ms 62828 KB Output is correct
10 Correct 66 ms 62892 KB Output is correct
11 Correct 65 ms 62912 KB Output is correct
12 Correct 65 ms 63028 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 63500 KB Output is correct
2 Correct 235 ms 64248 KB Output is correct
3 Correct 288 ms 64248 KB Output is correct
4 Correct 375 ms 64248 KB Output is correct
5 Correct 423 ms 64288 KB Output is correct
6 Correct 449 ms 64288 KB Output is correct
7 Correct 401 ms 64416 KB Output is correct
8 Correct 405 ms 64416 KB Output is correct
9 Correct 388 ms 64416 KB Output is correct
10 Correct 380 ms 64416 KB Output is correct
11 Correct 383 ms 64432 KB Output is correct
12 Correct 383 ms 64432 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 64432 KB Output is correct
2 Correct 187 ms 64680 KB Output is correct
3 Correct 243 ms 64700 KB Output is correct
4 Correct 449 ms 64700 KB Output is correct
5 Correct 707 ms 65584 KB Output is correct
6 Correct 773 ms 65592 KB Output is correct
7 Correct 387 ms 65592 KB Output is correct
8 Correct 745 ms 67032 KB Output is correct
9 Correct 569 ms 68296 KB Output is correct
10 Correct 619 ms 69784 KB Output is correct
11 Correct 623 ms 70936 KB Output is correct
12 Correct 613 ms 72104 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 72104 KB Output is correct
2 Correct 511 ms 72104 KB Output is correct
3 Correct 359 ms 72104 KB Output is correct
4 Correct 452 ms 72104 KB Output is correct
5 Correct 776 ms 72416 KB Output is correct
6 Correct 753 ms 72416 KB Output is correct
7 Correct 741 ms 72416 KB Output is correct
8 Correct 731 ms 72480 KB Output is correct
9 Correct 564 ms 72480 KB Output is correct
10 Correct 567 ms 72480 KB Output is correct
11 Correct 565 ms 72488 KB Output is correct
12 Correct 578 ms 72488 KB Output is correct