oj.uz

Submission #827134

# Submission time Handle Problem Language Result Execution time Memory
827134 2023-08-16T09:09:02 Z ttamx Distributing Candies (IOI21_candies) C++17
100 / 100
 441 ms 49708 KB 
#include "candies.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int inf=1e9;
const ll inf2=1e18;

typedef pair<ll,int> p2;

const int N=2e5+5;
const int K=1<<19;

int n,q;
vector<p2> qr[N];

struct segtree{
    struct node{
        p2 mn,mx;
        node(ll val=0,int id=0):mn(val,id),mx(val,id){}
        node(ll mn,ll mx,int id):mn(mn,id),mx(mx,id){}
        node& operator+=(const ll &o){
            mn.first+=o;
            mx.first+=o;
            return *this;
        }
        friend node operator+(node a,node b){
            node c;
            c.mn=min(a.mn,b.mn);
            c.mx=max(a.mx,b.mx);
            return c;
        }
    }t[K];
    ll lz[K];
    void pushlz(int l,int r,int i){
        t[i]+=lz[i];
        if(l<r){
            lz[i*2]+=lz[i];
            lz[i*2+1]+=lz[i];
        }
        lz[i]=0;
    }
    void build(int l,int r,int i){
        if(l==r)return void(t[i]=node(0,l));
        int m=(l+r)/2;
        build(l,m,i*2);
        build(m+1,r,i*2+1);
        t[i]=t[i*2]+t[i*2+1];
    }
    void build(){
        build(1,q,1);
    }
    void update(int l,int r,int i,int x,int y,ll v){
        pushlz(l,r,i);
        if(y<l||r<x)return;
        if(x<=l&&r<=y)return lz[i]=v,pushlz(l,r,i),void();
        int m=(l+r)/2;
        update(l,m,i*2,x,y,v);
        update(m+1,r,i*2+1,x,y,v);
        t[i]=t[i*2]+t[i*2+1];
    }
    void update(int x,int y,ll v){
        update(1,q,1,x,y,v);
    }
    node query(int l,int r,int i,ll c,node res){
        if(l==r)return t[i]+res;
        int m=(l+r)/2;
        pushlz(l,m,i*2);
        pushlz(m+1,r,i*2+1);
        auto res2=res+t[i*2+1];
        if(res2.mx.first-res2.mn.first>=c)return query(m+1,r,i*2+1,c,res);
        return query(l,m,i*2,c,res2);
    }
    node query(ll c){
        return query(1,q,1,c,node(inf2,-inf2,0));
    }
}s;

vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v) {
    n=c.size();
    q=l.size()+2;
    vector<int> ans(n);
    ll sum=0;
    s.build();
    s.update(1,q,inf);
    s.update(2,q,-inf);
    for(int i=0;i<q-2;i++){
        qr[l[i]].emplace_back(v[i],i+3);
        qr[r[i]+1].emplace_back(-v[i],i+3);
    }
    for(int i=0;i<n;i++){
        for(auto [val,id]:qr[i]){
            sum+=val;
            s.update(id,q,val);
        }
        auto tmp=s.query(c[i]);
        if(tmp.mx.second>tmp.mn.second)ans[i]=sum-(tmp.mx.first-c[i]);
        else ans[i]=sum-tmp.mn.first;
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21332 KB Output is correct
2 Correct 8 ms 21312 KB Output is correct
3 Correct 10 ms 21620 KB Output is correct
4 Correct 9 ms 21568 KB Output is correct
5 Correct 10 ms 21560 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 43028 KB Output is correct
2 Correct 435 ms 43420 KB Output is correct
3 Correct 407 ms 43408 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21420 KB Output is correct
2 Correct 254 ms 39452 KB Output is correct
3 Correct 99 ms 25404 KB Output is correct
4 Correct 441 ms 43424 KB Output is correct
5 Correct 405 ms 49248 KB Output is correct
6 Correct 414 ms 49708 KB Output is correct
7 Correct 401 ms 49080 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21308 KB Output is correct
2 Correct 9 ms 21420 KB Output is correct
3 Correct 124 ms 36956 KB Output is correct
4 Correct 93 ms 24436 KB Output is correct
5 Correct 229 ms 39348 KB Output is correct
6 Correct 219 ms 43256 KB Output is correct
7 Correct 222 ms 43828 KB Output is correct
8 Correct 226 ms 42504 KB Output is correct
9 Correct 239 ms 43824 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21332 KB Output is correct
2 Correct 8 ms 21312 KB Output is correct
3 Correct 10 ms 21620 KB Output is correct
4 Correct 9 ms 21568 KB Output is correct
5 Correct 10 ms 21560 KB Output is correct
6 Correct 429 ms 43028 KB Output is correct
7 Correct 435 ms 43420 KB Output is correct
8 Correct 407 ms 43408 KB Output is correct
9 Correct 8 ms 21420 KB Output is correct
10 Correct 254 ms 39452 KB Output is correct
11 Correct 99 ms 25404 KB Output is correct
12 Correct 441 ms 43424 KB Output is correct
13 Correct 405 ms 49248 KB Output is correct
14 Correct 414 ms 49708 KB Output is correct
15 Correct 401 ms 49080 KB Output is correct
16 Correct 9 ms 21308 KB Output is correct
17 Correct 9 ms 21420 KB Output is correct
18 Correct 124 ms 36956 KB Output is correct
19 Correct 93 ms 24436 KB Output is correct
20 Correct 229 ms 39348 KB Output is correct
21 Correct 219 ms 43256 KB Output is correct
22 Correct 222 ms 43828 KB Output is correct
23 Correct 226 ms 42504 KB Output is correct
24 Correct 239 ms 43824 KB Output is correct
25 Correct 9 ms 21332 KB Output is correct
26 Correct 90 ms 25188 KB Output is correct
27 Correct 264 ms 41804 KB Output is correct
28 Correct 427 ms 47576 KB Output is correct
29 Correct 417 ms 48044 KB Output is correct
30 Correct 404 ms 48148 KB Output is correct
31 Correct 405 ms 48344 KB Output is correct
32 Correct 409 ms 48552 KB Output is correct