oj.uz

Submission #488545

# Submission time Handle Problem Language Result Execution time Memory
488545 2021-11-19T14:57:23 Z ETK Distributing Candies (IOI21_candies) C++17
100 / 100
 438 ms 33628 KB 
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2e5+5;
int n,m;
ll sum[N<<2],mx[N<<2],mn[N<<2];//区间和，前缀最值
struct node{int x,v;};
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((L+R)>>1)
void up(int p){
    sum[p]=sum[ls]+sum[rs];
    mx[p]=max(mx[ls],sum[ls]+mx[rs]);
    mn[p]=min(mn[ls],sum[ls]+mn[rs]);
}
void modify(int p,int L,int R,int x,int v){
    if(L>x||R<x)return;
    if(L==R){
        sum[p]+=v;
        mx[p]=mn[p]=sum[p];
        return;
    }
    modify(ls,L,mid,x,v),modify(rs,mid+1,R,x,v);
    up(p);
}
int query(int p,int L,int R,int v,int lim){//线段树上二分
    //找到位置直接做
    if(L==R)return min((ll)lim,max(0ll,v+sum[p]));
    //若右边超限制
    if(mx[rs]-mn[rs]>=lim)return query(rs,mid+1,R,v,lim);
    //否则先做左边
    v=query(ls,L,mid,v,lim);
    //如果右边会<0
    if(v+mn[rs]<0)return sum[rs]-mn[rs];
    //如果右边会>lim
    if(v+mx[rs]>lim)return sum[rs]-(mx[rs]-lim);
    return v+sum[rs];
}
vi distribute_candies(vi c,vi l,vi r,vi v){
    n=c.size(),m=l.size();
    vi s;
    vector <node> Q[N];
    rep(i,0,m-1){
        int L=l[i],R=r[i],V=v[i];
        Q[L].pb({i+1,V}),Q[R+1].pb({i+1,-V});
    }
    rep(i,0,n-1){//扫描线
        for(auto t:Q[i]){
            modify(1,1,m,t.x,t.v);
        }
        s.pb(query(1,1,m,0,c[i]));
    }
    return s;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 4 ms 5176 KB Output is correct
4 Correct 4 ms 5180 KB Output is correct
5 Correct 6 ms 5196 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 32872 KB Output is correct
2 Correct 369 ms 33576 KB Output is correct
3 Correct 435 ms 33592 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5016 KB Output is correct
2 Correct 197 ms 27584 KB Output is correct
3 Correct 55 ms 10644 KB Output is correct
4 Correct 419 ms 33612 KB Output is correct
5 Correct 347 ms 33628 KB Output is correct
6 Correct 402 ms 33596 KB Output is correct
7 Correct 357 ms 33596 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 96 ms 25324 KB Output is correct
4 Correct 54 ms 9020 KB Output is correct
5 Correct 150 ms 30344 KB Output is correct
6 Correct 178 ms 30484 KB Output is correct
7 Correct 153 ms 30340 KB Output is correct
8 Correct 166 ms 30360 KB Output is correct
9 Correct 194 ms 30404 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 4 ms 5176 KB Output is correct
4 Correct 4 ms 5180 KB Output is correct
5 Correct 6 ms 5196 KB Output is correct
6 Correct 359 ms 32872 KB Output is correct
7 Correct 369 ms 33576 KB Output is correct
8 Correct 435 ms 33592 KB Output is correct
9 Correct 3 ms 5016 KB Output is correct
10 Correct 197 ms 27584 KB Output is correct
11 Correct 55 ms 10644 KB Output is correct
12 Correct 419 ms 33612 KB Output is correct
13 Correct 347 ms 33628 KB Output is correct
14 Correct 402 ms 33596 KB Output is correct
15 Correct 357 ms 33596 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 96 ms 25324 KB Output is correct
19 Correct 54 ms 9020 KB Output is correct
20 Correct 150 ms 30344 KB Output is correct
21 Correct 178 ms 30484 KB Output is correct
22 Correct 153 ms 30340 KB Output is correct
23 Correct 166 ms 30360 KB Output is correct
24 Correct 194 ms 30404 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 65 ms 9192 KB Output is correct
27 Correct 220 ms 28360 KB Output is correct
28 Correct 351 ms 33584 KB Output is correct
29 Correct 438 ms 33532 KB Output is correct
30 Correct 344 ms 33568 KB Output is correct
31 Correct 372 ms 33596 KB Output is correct
32 Correct 365 ms 33552 KB Output is correct