oj.uz

Submission #699534

# Submission time Handle Problem Language Result Execution time Memory
699534 2023-02-17T09:11:48 Z Dan4Life Sterilizing Spray (JOI15_sterilizing) C++17
20 / 100
 155 ms 12572 KB 
#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();
}

Compilation message

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.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8888 KB Output is correct
2 Correct 71 ms 7748 KB Output is correct
3 Correct 67 ms 10692 KB Output is correct
4 Correct 100 ms 12300 KB Output is correct
5 Correct 107 ms 12492 KB Output is correct
6 Correct 103 ms 12572 KB Output is correct
7 Correct 121 ms 12436 KB Output is correct
8 Correct 119 ms 12504 KB Output is correct
9 Correct 99 ms 12492 KB Output is correct
10 Correct 100 ms 12448 KB Output is correct
11 Correct 115 ms 12464 KB Output is correct
12 Correct 96 ms 12512 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5500 KB Output is correct
2 Correct 32 ms 8176 KB Output is correct
3 Correct 42 ms 8188 KB Output is correct
4 Correct 84 ms 6784 KB Output is correct
5 Correct 155 ms 12140 KB Output is correct
6 Correct 140 ms 12108 KB Output is correct
7 Correct 93 ms 12156 KB Output is correct
8 Correct 138 ms 12048 KB Output is correct
9 Correct 127 ms 12048 KB Output is correct
10 Correct 137 ms 12092 KB Output is correct
11 Correct 122 ms 12128 KB Output is correct
12 Correct 129 ms 12084 KB Output is correct

Subtask #4
0 / 75.0

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