oj.uz

Submission #862141

# Submission time Handle Problem Language Result Execution time Memory
862141 2023-10-17T14:39:02 Z sunwukong123 Distributing Candies (IOI21_candies) C++17
100 / 100
 1160 ms 72140 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 200005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 

struct node {
    int s,e,m,lazy;
    pi val,mn,mx;
    node *l, *r;
    node(int _s, int _e){
        s=_s;e=_e;m=(s+e)/2;
        lazy=0;
        val=mx={0,e};
        mn={0,-e};
        if(s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    void value(){
        if(lazy==0)return;
        if(s==e){
            mn.first+=lazy;
            mx.first+=lazy;
            val.first+=lazy;
            lazy=0;
            return ;
        }
        val.first+=lazy;
        mn.first+=lazy;
        mx.first+=lazy;
        l->lazy+=lazy;
        r->lazy+=lazy;
        lazy=0;
        return;
    }
    void update(int x, int y, int nval){
        value();
        if(s==x&&e==y){
            lazy+=nval;
            return;
        }
        if(x>m)r->update(x,y,nval);
        else if(y<=m)l->update(x,y,nval);
        else l->update(x,m,nval),r->update(m+1,y,nval);
        l->value(),r->value();
        mn=min(l->mn,r->mn);
        mx=max(l->mx,r->mx);
        val={l->val.first+r->val.first,val.second};
    }
    int query(int x, int y){
        value();
        if(s==x&&e==y)return val.first;
        if(x>m)return r->query(x,y);
        else if(y<=m)return l->query(x,y);
        else return l->query(x,m) + query(m+1,y);
    }
    pi query_max(int x, int y){
        value();
        if(s==x&&e==y)return mx;
        if(x>m)return r->query_max(x,y);
        else if(y<=m)return l->query_max(x,y);
        else return max(l->query_max(x,m), r->query_max(m+1,y));
    }
    pi query_min(int x, int y){
        value();
        if(s==x&&e==y)return mn;
        if(x>m)return r->query_min(x,y);
        else if(y<=m)return l->query_min(x,y);
        else return min(l->query_min(x,m), r->query_min(m+1,y));
    }

}*seg;

vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l,
                                    vector<int32_t> r, vector<int32_t> v) {
    int n=c.size();
    vector<pi> A[n+5];
    int Q=l.size();
    seg=new node(0,Q+3); // 0 is just set to 0 for everything
    for(int t=0;t<Q;t++){
        A[l[t]].push_back({v[t],t+1});
        A[r[t]+1].push_back({-v[t],t+1});
    }
    vector<int32_t>res;
    for(int i=0;i<=n-1;i++){
        //debug(i);
        for(auto x:A[i]){
            //debug(x.first,x.second);
            seg->update(x.second,Q+3,x.first);
        }

        int lo=0,hi=Q+2;
        while(lo<hi-1){
            int mi=(lo+hi)/2;
            pi MX=seg->query_max(mi,Q+3);
            pi MN=seg->query_min(mi,Q+3);
            if(MX.first-MN.first>=c[i]){
                lo=mi;
            } else{
                hi=mi;
            }
        }
        //debug(lo);
        pi MN=seg->query_min(lo,Q+3);
        pi MX=seg->query_max(lo,Q+3);
        MN.second*=-1;
        int F=seg->query(Q+3,Q+3);
        //debug(MN.first,MX.first,MN.second,MX.second,F);

        if((lo == 0 && MX.first<=c[i])|| MN.second>MX.second){
            res.push_back(F-MN.first);
        } else {
            res.push_back((int)c[i]+(F-MX.first));
        }
    }
    return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 997 ms 71044 KB Output is correct
2 Correct 1150 ms 70572 KB Output is correct
3 Correct 1160 ms 69568 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 366 ms 59904 KB Output is correct
3 Correct 197 ms 10820 KB Output is correct
4 Correct 957 ms 70312 KB Output is correct
5 Correct 960 ms 70608 KB Output is correct
6 Correct 833 ms 70864 KB Output is correct
7 Correct 832 ms 70672 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 112 ms 58960 KB Output is correct
4 Correct 146 ms 9352 KB Output is correct
5 Correct 536 ms 65540 KB Output is correct
6 Correct 488 ms 66572 KB Output is correct
7 Correct 399 ms 66472 KB Output is correct
8 Correct 542 ms 65448 KB Output is correct
9 Correct 572 ms 67164 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct
6 Correct 997 ms 71044 KB Output is correct
7 Correct 1150 ms 70572 KB Output is correct
8 Correct 1160 ms 69568 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 366 ms 59904 KB Output is correct
11 Correct 197 ms 10820 KB Output is correct
12 Correct 957 ms 70312 KB Output is correct
13 Correct 960 ms 70608 KB Output is correct
14 Correct 833 ms 70864 KB Output is correct
15 Correct 832 ms 70672 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 440 KB Output is correct
18 Correct 112 ms 58960 KB Output is correct
19 Correct 146 ms 9352 KB Output is correct
20 Correct 536 ms 65540 KB Output is correct
21 Correct 488 ms 66572 KB Output is correct
22 Correct 399 ms 66472 KB Output is correct
23 Correct 542 ms 65448 KB Output is correct
24 Correct 572 ms 67164 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 175 ms 9424 KB Output is correct
27 Correct 372 ms 60256 KB Output is correct
28 Correct 997 ms 71400 KB Output is correct
29 Correct 1008 ms 71792 KB Output is correct
30 Correct 929 ms 71844 KB Output is correct
31 Correct 889 ms 72068 KB Output is correct
32 Correct 846 ms 72140 KB Output is correct