oj.uz

Submission #77978

# Submission time Handle Problem Language Result Execution time Memory
77978 2018-10-01T14:45:58 Z nxteru Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 813 ms 96100 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){
            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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 61944 KB Output is correct
2 Incorrect 55 ms 62080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 65324 KB Output is correct
2 Correct 200 ms 65324 KB Output is correct
3 Correct 262 ms 65700 KB Output is correct
4 Correct 552 ms 66540 KB Output is correct
5 Correct 804 ms 69152 KB Output is correct
6 Correct 750 ms 70644 KB Output is correct
7 Incorrect 758 ms 72068 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 72068 KB Output is correct
2 Correct 508 ms 73044 KB Output is correct
3 Correct 362 ms 74284 KB Output is correct
4 Correct 514 ms 75804 KB Output is correct
5 Correct 785 ms 79240 KB Output is correct
6 Correct 813 ms 81692 KB Output is correct
7 Correct 770 ms 84464 KB Output is correct
8 Correct 768 ms 86800 KB Output is correct
9 Correct 628 ms 89064 KB Output is correct
10 Correct 615 ms 91312 KB Output is correct
11 Correct 596 ms 93624 KB Output is correct
12 Correct 637 ms 96100 KB Output is correct