oj.uz

Submission #874228

# Submission time Handle Problem Language Result Execution time Memory
874228 2023-11-16T13:08:49 Z 8pete8 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 357 ms 134892 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include <iomanip>  
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,int>
#define vi vector<int>
#define pb push_back
//#define p push
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
#define double long double
const int mxn=1e5,inf=1e9,lg=35;
int n,k;
bool yes=false;
struct seg{
    int v[4*mxn+10][lg+5],add[4*mxn+10],cur[4*mxn+10];
    void init(){
        for(int i=0;i<4*mxn+10;i++){
            for(int j=0;j<=lg;j++)v[i][j]=0;
            add[i]=cur[i]=0;
        }
    }
    void push(int pos,int l,int r){
        if(!add[pos])return;
        cur[pos]+=add[pos];
        cur[pos]=min(cur[pos],lg);
        v[pos][0]=v[pos][cur[pos]];
        if(l!=r){
            add[pos<<1]+=add[pos];
            add[(pos<<1)^1]+=add[pos];
        }
        add[pos]=0;
    }
    void updr(int l,int r,int ql,int qr,int pos){
        push(pos,l,r);
        if(r<ql||l>qr)return;
        if(l>=ql&&r<=qr){
            add[pos]++;
            push(pos,l,r);
            return;
        }
        int mid=l+(r-l)/2;
        updr(l,mid,ql,qr,(pos<<1));
        updr(mid+1,r,ql,qr,(pos<<1)^1);
        for(int j=0;j<=lg;j++)v[pos][j]=v[pos<<1][min(cur[pos<<1]+j,lg)]+v[(pos<<1)^1][min(cur[(pos<<1)^1]+j,lg)];
        cur[pos]=0;
    }
    void updp(int l,int r,int qp,int pos,int val){
        push(pos,l,r);
        if(l>r)return;
        cur[pos]=0;
        if(l==r){
            for(int j=0;j<=lg;j++)v[pos][j]=val,val/=k;
            add[pos]=0;
            return;
        }
        int mid=l+(r-l)/2;
        if(qp<=mid)updp(l,mid,qp,(pos<<1),val);
        else updp(mid+1,r,qp,(pos<<1)^1,val);
        push(pos<<1,l,mid);
        push((pos<<1)^1,mid+1,r);
        for(int j=0;j<=lg;j++)v[pos][j]=v[pos<<1][min(cur[pos<<1]+j,lg)]+v[(pos<<1)^1][min(cur[(pos<<1)^1]+j,lg)];
    }
    int qry(int l,int r,int ql,int qr,int pos){
        push(pos,l,r);
        if(r<ql||l>qr)return 0;
        if(l>=ql&&r<=qr)return v[pos][0];
        int mid=l+(r-l)/2;
        return qry(l,mid,ql,qr,pos<<1)+qry(mid+1,r,ql,qr,(pos<<1)^1);
    }
}s;
int32_t main(){
    fastio
    int q;cin>>n>>q>>k;
    s.init();
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        s.updp(1,n,i,1,a);
    }
    while(q--){
        int t,a,b;cin>>t>>a>>b;
        if(k==1&&t==2)continue;
        if(t==1)s.updp(1,n,a,1,b);
        else if(t==2)s.updr(1,n,a,b,1);
        else cout<<s.qry(1,n,a,b,1)<<"\n";
    }
    return 0;
}

Compilation message

sterilizing.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
sterilizing.cpp:40:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   40 |     void init(){
      |               ^
sterilizing.cpp:46:34: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 |     void push(int pos,int l,int r){
      |                                  ^
sterilizing.cpp:57:48: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   57 |     void updr(int l,int r,int ql,int qr,int pos){
      |                                                ^
sterilizing.cpp:71:49: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   71 |     void updp(int l,int r,int qp,int pos,int val){
      |                                                 ^
sterilizing.cpp:87:46: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   87 |     int qry(int l,int r,int ql,int qr,int pos){
      |                                              ^
sterilizing.cpp:95:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   95 | int32_t main(){
      |              ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 131920 KB Output is correct
2 Correct 22 ms 131824 KB Output is correct
3 Correct 21 ms 131928 KB Output is correct
4 Correct 24 ms 131916 KB Output is correct
5 Correct 26 ms 131932 KB Output is correct
6 Correct 24 ms 131924 KB Output is correct
7 Correct 24 ms 132000 KB Output is correct
8 Correct 28 ms 131932 KB Output is correct
9 Correct 24 ms 131932 KB Output is correct
10 Correct 23 ms 131932 KB Output is correct
11 Correct 24 ms 131924 KB Output is correct
12 Correct 24 ms 131924 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 134280 KB Output is correct
2 Correct 126 ms 133984 KB Output is correct
3 Correct 163 ms 133992 KB Output is correct
4 Correct 212 ms 134560 KB Output is correct
5 Correct 242 ms 134800 KB Output is correct
6 Correct 236 ms 134736 KB Output is correct
7 Correct 234 ms 134756 KB Output is correct
8 Correct 231 ms 134892 KB Output is correct
9 Correct 224 ms 134740 KB Output is correct
10 Correct 222 ms 134740 KB Output is correct
11 Correct 218 ms 134624 KB Output is correct
12 Correct 226 ms 134600 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 132312 KB Output is correct
2 Correct 85 ms 132176 KB Output is correct
3 Correct 99 ms 132332 KB Output is correct
4 Correct 171 ms 132992 KB Output is correct
5 Correct 302 ms 133204 KB Output is correct
6 Correct 315 ms 133340 KB Output is correct
7 Correct 215 ms 133656 KB Output is correct
8 Correct 308 ms 133204 KB Output is correct
9 Correct 270 ms 133292 KB Output is correct
10 Correct 260 ms 133296 KB Output is correct
11 Correct 261 ms 133200 KB Output is correct
12 Correct 272 ms 133100 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 133648 KB Output is correct
2 Correct 200 ms 133628 KB Output is correct
3 Correct 142 ms 133204 KB Output is correct
4 Correct 185 ms 133772 KB Output is correct
5 Correct 334 ms 134624 KB Output is correct
6 Correct 357 ms 134564 KB Output is correct
7 Correct 333 ms 134480 KB Output is correct
8 Correct 314 ms 134480 KB Output is correct
9 Correct 305 ms 134408 KB Output is correct
10 Correct 267 ms 134480 KB Output is correct
11 Correct 277 ms 134500 KB Output is correct
12 Correct 277 ms 134368 KB Output is correct