oj.uz

답안 #521358

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521358 2022-02-01T23:46:12 Z perchuts Sterilizing Spray (JOI15_sterilizing) C++17
20 / 100
 557 ms 524292 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);

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; }
pair<ii,vector<int>>lazy[4*maxn];
int n,q;
ll k;
ll v[maxn],seg[4*maxn];

void build(int i,int l,int r){
    if(l==r){
        seg[i] = v[l];
        ll tmp = v[l];
        while(true&&k!=1){lazy[i].second.pb(tmp/k);if(!(tmp/k))break;tmp/=k;}
        lazy[i].first={-1,0};
        return;
    }
    int md = (l+r)/2;
    build(2*i,l,md);
    build(2*i+1,md+1,r);
    seg[i] = seg[2*i] + seg[2*i+1];
    int j = 0;
    while(true&&k!=1){
        int le = (j>=sz(lazy[2*i].second) ? 0 : lazy[2*i].second[j]);
        int ri = (j>=sz(lazy[2*i+1].second) ? 0 : lazy[2*i+1].second[j++]);
        lazy[i].second.pb(le+ri);
        if(le+ri==0)break; 
    }   
    lazy[i].first={-1,0};
}

void push(int i,int l,int r){
    auto [ind,add] = lazy[i].first;
    if(!add)return;
    ind = min(sz(lazy[i].second)-1,ind+add);
    seg[i] = lazy[i].second[ind];
    lazy[i].first.second = 0;
    if(l==r)return;
    lazy[2*i].first.second+=add;
    lazy[2*i+1].first.second+=add;
}

void update(int i,int l,int r,int x,int d){
    if(k!=1)push(i,l,r);
    if(l>x||r<x)return;
    if(l==r){
        seg[i] = d;
        lazy[i].second.clear();
        ll tmp = d;
        while(true&&k!=1){lazy[i].second.pb(tmp/k);if(!(tmp/k))break;tmp/=k;}
        lazy[i].first={-1,0};
        return;
    }
    int md = (l+r)/2;
    update(2*i,l,md,x,d);
    update(2*i+1,md+1,r,x,d);
    lazy[i].second.clear();
    int j = 0;
    while(true&&k!=1){
        int le = (j>=sz(lazy[2*i].second) ? 0 : lazy[2*i].second[j]);
        int ri = (j>=sz(lazy[2*i+1].second) ? 0 : lazy[2*i+1].second[j++]);
        lazy[i].second.pb(le+ri);
        if(le+ri==0)break; 
    }   
    seg[i] = seg[2*i] + seg[2*i+1];
    lazy[i].first={-1,0};
}

void update2(int i,int l,int r,int x,int y){
    if(k!=1)push(i,l,r);
    if(l>y||r<x)return;
    if(x<=l&&r<=y){
        lazy[i].first.second++;
        push(i,l,r);
        return;
    }
    int md = (l+r)/2;
    update2(2*i,l,md,x,y);
    update2(2*i+1,md+1,r,x,y);
    seg[i] = seg[2*i] + seg[2*i+1];
}


ll query(int i,int l,int r,int x,int y){
    if(k!=1)push(i,l,r);
    if(l>y||r<x)return 0;
    if(x<=l&&r<=y)return 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 debug(int i,int l,int r){
    if(l==r){
        cout<<l<<" "<<r<<" "<<seg[i]<<endl;return;
    }
    int md = (l+r)/2;
    debug(2*i,l,md);
    debug(2*i+1,md+1,r);
    cout<<l<<" "<<r<<" "<<seg[i]<<endl;
}




int main(){_
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++)cin>>v[i];
    build(1,1,n);
    // for(auto x:lazy[1].second)cout<<x<<" ";
    // cout<<endl;
    while(q--){
        int t,a,b;cin>>t>>a>>b;
        // cout<<endl<<endl;
        // debug(1,1,n);
        if(t==1){   
            update(1,1,n,a,b);
        }else if(t==2){
            if(k!=1)update2(1,1,n,a,b);
        }else{
            cout<<query(1,1,n,a,b)<<endl;
        }
    }
    // cout<<"query"<<endl;
    // debug(1,1,n);
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 555 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 16568 KB Output is correct
2 Correct 49 ms 16076 KB Output is correct
3 Correct 50 ms 17340 KB Output is correct
4 Correct 58 ms 18144 KB Output is correct
5 Correct 66 ms 18600 KB Output is correct
6 Correct 80 ms 18688 KB Output is correct
7 Correct 64 ms 18488 KB Output is correct
8 Correct 64 ms 18544 KB Output is correct
9 Correct 73 ms 18408 KB Output is correct
10 Correct 70 ms 18364 KB Output is correct
11 Correct 60 ms 18440 KB Output is correct
12 Correct 74 ms 18440 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 13800 KB Output is correct
2 Correct 30 ms 17276 KB Output is correct
3 Correct 40 ms 17312 KB Output is correct
4 Correct 94 ms 16260 KB Output is correct
5 Correct 159 ms 23344 KB Output is correct
6 Correct 146 ms 23344 KB Output is correct
7 Correct 62 ms 17220 KB Output is correct
8 Correct 146 ms 23312 KB Output is correct
9 Correct 106 ms 23224 KB Output is correct
10 Correct 105 ms 23220 KB Output is correct
11 Correct 129 ms 23212 KB Output is correct
12 Correct 112 ms 23196 KB Output is correct

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 557 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -