제출 #699534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699534		Dan4Life	Sterilizing Spray (JOI15_sterilizing)	C++17	20 / 100	155 ms	12572 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll // delete if causing problems
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define mod(a) (a+MOD)%MOD
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()

const int mxN = (int)3e5+10; // change when needed!
int n, k, q, a[mxN];
struct Data{
    int mx, mx2, mxcnt, sum;
} segTree[2*mxN];
int lazy[2*mxN];

void prop(int p, int l, int r){
    if(l==r or lazy[p]<0) return;
    int m = (l+r)/2;
    int lp = p+1, rp = p+2*(m-l+1);
    lazy[lp]=lazy[rp]=lazy[p];
    segTree[lp].mx=segTree[rp].mx=segTree[p].mx;
    segTree[lp].mx2=segTree[rp].mx2=segTree[p].mx2;
    segTree[lp].mxcnt=(m-l+1), segTree[p].mxcnt=(r-m);
    segTree[lp].sum=(m-l+1)*segTree[lp].mx;
    segTree[rp].sum=(r-m)*segTree[rp].mx;
    lazy[p]=-1;
}

Data combine(Data &a, Data &b){
    Data c; c.sum=a.sum+b.sum;
    if(a.mx>b.mx){
        c.mx=a.mx; c.mxcnt=a.mxcnt;
        if(a.mx2>b.mx) c.mx2=a.mx2;
        else c.mx2=b.mx;
    }
    else if(a.mx<b.mx){
        c.mx=b.mx; c.mxcnt=b.mxcnt;
        if(b.mx2>a.mx) c.mx2=b.mx2;
        else c.mx2=a.mx;
    }
    else{
        c.mx=a.mx, c.mxcnt=a.mxcnt+b.mxcnt;
        if(a.mx2>b.mx2)c.mx2=a.mx2;
        else c.mx2=b.mx2;
    }
    return c;
}

void upd(int i, int j, int v, int t, int p=0, int l=1, int r=n){
    if(i>r or j<l or i>j) return; prop(p,l,r);
    int m = (l+r)/2; int lp = p+1, rp = p+2*(m-l+1);
    if(i<=l and r<=j){
        if(!t){
            segTree[p].sum=segTree[p].mx=v;
            segTree[p].mxcnt=1, segTree[p].mx2=-1;
            return;
        }
        if(segTree[p].mx<v){
            segTree[p].sum=0; lazy[p]=0;
            segTree[p].mx=0;
            segTree[p].mxcnt=(r-l+1);
            segTree[p].mx2=-1;
            return;
        }
        if(segTree[p].mx2<v){
            int nv = segTree[p].mx/v;
            segTree[p].sum=nv*segTree[p].mxcnt;
            lazy[p]=nv;
            //assign all elements in l to r = 0 (excluding those =mx)
            segTree[p].mx=nv;
            segTree[p].mxcnt=(r-l+1);
            segTree[p].mx2=-1;
            return;
        }
    }
    upd(i,j,v,t,lp,l,m),upd(i,j,v,t,rp,m+1,r);
    segTree[p] = combine(segTree[lp],segTree[rp]);
}

int query(int i, int j, int p=0, int l=1, int r=n){
    if(i>r or j<l or i>j) return 0; prop(p,l,r);
    if(i<=l and r<=j) return segTree[p].sum;
    int m = (l+r)/2; int lp=p+1, rp = p+2*(m-l+1);
    return query(i,j,lp,l,m)+query(i,j,rp,m+1,r);
}

void solve()
{
    cin >> n >> q >> k; fill(lazy,lazy+2*mxN,-1);
    for(int i = 1; i <= n; i++) cin >> a[i], upd(i,i,a[i],0);
    while(q--){
        int t, x, y; cin >> t >> x >> y;
        if(t==1) upd(x, x, y, 0);
        else if(t==2){
            if(k>1) upd(x, y, k, 1);
        }
        else cout << query(x,y) << "\n";
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
}

컴파일 시 표준 에러 (stderr) 메시지

sterilizing.cpp: In function 'void upd(ll, ll, ll, ll, ll, ll, ll)':
sterilizing.cpp:55:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   55 |     if(i>r or j<l or i>j) return; prop(p,l,r);
      |     ^~
sterilizing.cpp:55:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   55 |     if(i>r or j<l or i>j) return; prop(p,l,r);
      |                                   ^~~~
sterilizing.cpp: In function 'll query(ll, ll, ll, ll, ll)':
sterilizing.cpp:86:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   86 |     if(i>r or j<l or i>j) return 0; prop(p,l,r);
      |     ^~
sterilizing.cpp:86:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   86 |     if(i>r or j<l or i>j) return 0; prop(p,l,r);
      |                                     ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 75