oj.uz

답안 #521373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521373 2022-02-02T01:57:48 Z perchuts Sterilizing Spray (JOI15_sterilizing) C++17
5 / 100
 5000 ms 290884 KB 
#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define lim 35
using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

ll v[maxn];
queue<ll>seg[4*maxn];
int lazy[4*maxn];
int n,q,k;

ll front(queue<ll>x){return x.empty()?0:x.front();}

void updateNode(int i){
    queue<ll>l = seg[2*i], r = seg[2*i+1];
    if(sz(l)<sz(r))swap(l,r);
    while(!seg[i].empty())seg[i].pop();
    while(!l.empty()){
        ll sum = front(l) + front(r);
        l.pop();if(!r.empty())r.pop();
        seg[i].push(sum);
    }
}

void push(int i,int l,int r){
    for(int j=1;j<=lazy[i];j++)if(!seg[i].empty())seg[i].pop();
    if(l!=r)lazy[2*i]+=lazy[i],lazy[2*i+1]+=lazy[i];
    lazy[i] = 0;
}

void update(int i,int l,int r,int x,ll d){
    push(i,l,r);
    if(l>x||r<x)return;
    if(l==r){
        while(!seg[i].empty())seg[i].pop();
        for(;d&&sz(seg[i])<lim;d/=k)seg[i].push(d);
        return; 
    }
    int md = (l+r)/2;
    update(2*i,l,md,x,d);
    update(2*i+1,md+1,r,x,d);
    updateNode(i);
}

ll query(int i,int l,int r,int x,int y){
    push(i,l,r);
    if(l>y||r<x)return 0;
    if(x<=l&&r<=y)return front(seg[i]);
    int md = (l+r)/2;
    return query(2*i,l,md,x,y) + query(2*i+1,md+1,r,x,y);
}   

void spray(int i,int l,int r,int x,int y){
    push(i,l,r);
    if(l>y||r<x)return;
    if(x<=l&&r<=y){
        lazy[i]++;
        push(i,l,r);
        return;
    }
    int md = (l+r)/2;
    spray(2*i,l,md,x,y);
    spray(2*i+1,md+1,r,x,y);
    updateNode(i);
}


int main(){_
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++){
        ll x;cin>>x;
        update(1,1,n,i,x);
    }   
    while(q--){
        int t,a,b;cin>>t>>a>>b;
        if(t==1){
            update(1,1,n,a,1LL*b);
        }else if(t==2){
            if(k!=1)spray(1,1,n,a,b);
        }else{
            cout<<query(1,1,n,a,b)<<endl;
        }
    }
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 269636 KB Output is correct
2 Correct 229 ms 270276 KB Output is correct
3 Correct 218 ms 269896 KB Output is correct
4 Correct 327 ms 270048 KB Output is correct
5 Correct 304 ms 269832 KB Output is correct
6 Correct 241 ms 269812 KB Output is correct
7 Correct 310 ms 270132 KB Output is correct
8 Correct 288 ms 269920 KB Output is correct
9 Correct 330 ms 270004 KB Output is correct
10 Correct 281 ms 270100 KB Output is correct
11 Correct 277 ms 270100 KB Output is correct
12 Correct 294 ms 269880 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5066 ms 290884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 349 ms 269808 KB Output is correct
2 Correct 507 ms 270252 KB Output is correct
3 Correct 616 ms 270388 KB Output is correct
4 Correct 969 ms 270156 KB Output is correct
5 Correct 2415 ms 270960 KB Output is correct
6 Correct 2356 ms 270828 KB Output is correct
7 Execution timed out 5100 ms 286016 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2645 ms 272784 KB Output is correct
2 Correct 2832 ms 272472 KB Output is correct
3 Correct 4871 ms 283388 KB Output is correct
4 Correct 3423 ms 272676 KB Output is correct
5 Execution timed out 5099 ms 275360 KB Time limit exceeded
6 Halted 0 ms 0 KB -