oj.uz

Submission #789483

# Submission time Handle Problem Language Result Execution time Memory
789483 2023-07-21T12:42:08 Z winter0101 Food Court (JOI21_foodcourt) C++14
13 / 100
 374 ms 63636 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=2e5+5e4+9;
struct node{
long long mx,lazy;
bool mxup;
node(){
mx=0;
mxup=0;
lazy=0;
}
}st[maxn*4];
void push(int id){
if (st[id].mxup){
if (!st[id*2].mxup){
    st[id*2].mxup=1;
    st[id*2].mx=st[id].mx;
    st[id*2].lazy+=st[id].lazy;
}
else {
    st[id*2].mx=max(st[id*2].mx+st[id].lazy,st[id].mx);
    st[id*2].lazy+=st[id].lazy;
}
if (!st[id*2+1].mxup){
    st[id*2+1].mxup=1;
    st[id*2+1].mx=st[id].mx;
    st[id*2+1].lazy+=st[id].lazy;
}
else {
    st[id*2+1].mx=max(st[id*2+1].mx+st[id].lazy,st[id].mx);
    st[id*2+1].lazy+=st[id].lazy;
}
st[id].mx=0;
st[id].lazy=0;
st[id].mxup=0;
}
else {
    if (!st[id*2].mxup){
    st[id*2].lazy+=st[id].lazy;
    }
    else {
    st[id*2].mx+=st[id].lazy;
    }
    if (!st[id*2+1].mxup){
    st[id*2+1].lazy+=st[id].lazy;
    }
    else {
    st[id*2+1].mx+=st[id].lazy;
    }
    st[id].lazy=0;
}
}
void update(int id,int l,int r,int u,int v,long long val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
    if (!st[id].mxup){
        st[id].lazy+=val;
    }
    else {
        st[id].mx+=val;
        st[id].lazy+=val;
    }
    return;
}
int mid=(l+r)/2;
push(id);
update(id*2,l,mid,u,v,val);
update(id*2+1,mid+1,r,u,v,val);
}
void update2(int id,int l,int r,int u,int v,long long val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
    if (!st[id].mxup){
        st[id].mxup=1;
        st[id].mx=val;
    }
    else st[id].mx=max(st[id].mx,val);
    return;
}
int mid=(l+r)/2;
push(id);
update2(id*2,l,mid,u,v,val);
update2(id*2+1,mid+1,r,u,v,val);
}
long long get(int id,int l,int r,int u){
while (true){
if (l==r){
    return st[id].mx;
}
push(id);
int mid=(l+r)/2;
if (mid>=u){
    r=mid;
    id=id*2;
}
else {
    l=mid+1;
    id=id*2+1;
}
}
}
long long bit[maxn];
long long shop[maxn];
long long tk[maxn];
int n,m,q;
void add(int pos,long long val){
for(;pos<=q;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
long long get(int pos){
long long sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
long long get(int l,int r){
return get(r)-get(l-1);
}
struct range{
int l,r,c;
long long k;
}b[maxn];
vector<int>ad[maxn],dl[maxn];
vector<int>qr[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>m>>q;
    for1(i,1,n)update2(1,1,n,i,i,0);
    for1(i,1,q){
    int t;
    cin>>t;
    shop[i]=-1;
    if (t==3){
        int x;
        long long y;
        cin>>x>>y;
        qr[x].pb(i);
        tk[i]=y;
        shop[i]=get(1,1,n,x);
    }
    if (t==2){
        int l,r;
        long long k;
        cin>>l>>r>>k;
        update(1,1,n,l,r,-k);
        update2(1,1,n,l,r,0);
    }
    if (t==1){
        int l,r,c;
        long long k;
        cin>>l>>r>>c>>k;
        ad[l].pb(i);
        dl[r].pb(i);
        b[i]={l,r,c,k};
        update(1,1,n,l,r,k);
    }
    }
    for1(i,1,n){
    for (auto v:ad[i]){
        add(v,b[v].k);
    }
    for (auto v:qr[i]){
        //long long haveicecream=tk[v];
        if (shop[v]<tk[v]){
            shop[v]=0;
            continue;
        }
        long long diff=shop[v]-tk[v]+1;
        int l=1,r=v-1,asn=v;
        while (l<=r){
            int mid=(l+r)/2;
            if (get(mid,v)>=diff){
                asn=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        shop[v]=b[asn].c;
    }
    for (auto v:dl[i]){
        add(v,-b[v].k);
    }
    }
    for1(i,1,q){
    if (tk[i]){
        cout<<shop[i]<<'\n';
    }
    }



}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 47428 KB Output is correct
2 Correct 98 ms 47748 KB Output is correct
3 Correct 88 ms 47436 KB Output is correct
4 Correct 94 ms 47364 KB Output is correct
5 Correct 89 ms 47744 KB Output is correct
6 Correct 93 ms 47740 KB Output is correct
7 Correct 35 ms 45396 KB Output is correct
8 Correct 44 ms 45640 KB Output is correct
9 Correct 89 ms 46504 KB Output is correct
10 Correct 91 ms 47488 KB Output is correct
11 Correct 89 ms 47060 KB Output is correct
12 Correct 98 ms 47364 KB Output is correct
13 Incorrect 91 ms 47064 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 47748 KB Output is correct
2 Correct 92 ms 48368 KB Output is correct
3 Correct 85 ms 48588 KB Output is correct
4 Correct 66 ms 46404 KB Output is correct
5 Correct 80 ms 47520 KB Output is correct
6 Correct 86 ms 48384 KB Output is correct
7 Correct 42 ms 45972 KB Output is correct
8 Correct 44 ms 45672 KB Output is correct
9 Correct 65 ms 47224 KB Output is correct
10 Correct 62 ms 45652 KB Output is correct
11 Correct 78 ms 47352 KB Output is correct
12 Correct 83 ms 47424 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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