oj.uz

Submission #862124

# Submission time Handle Problem Language Result Execution time Memory
862124 2023-10-17T14:25:17 Z sunwukong123 Distributing Candies (IOI21_candies) C++17
67 / 100
 1171 ms 70204 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,s};
        mn={0,-s};
        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 || 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 348 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 1116 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 69328 KB Output is correct
2 Correct 1145 ms 69072 KB Output is correct
3 Correct 1171 ms 69064 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 392 ms 59632 KB Output is correct
3 Correct 216 ms 10424 KB Output is correct
4 Correct 1020 ms 70148 KB Output is correct
5 Correct 991 ms 70092 KB Output is correct
6 Correct 827 ms 70204 KB Output is correct
7 Correct 826 ms 69944 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 117 ms 59312 KB Output is correct
4 Correct 154 ms 9164 KB Output is correct
5 Correct 546 ms 65952 KB Output is correct
6 Correct 491 ms 66124 KB Output is correct
7 Correct 381 ms 66168 KB Output is correct
8 Correct 542 ms 66324 KB Output is correct
9 Correct 596 ms 66372 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 1116 KB Output is correct
6 Correct 1022 ms 69328 KB Output is correct
7 Correct 1145 ms 69072 KB Output is correct
8 Correct 1171 ms 69064 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 392 ms 59632 KB Output is correct
11 Correct 216 ms 10424 KB Output is correct
12 Correct 1020 ms 70148 KB Output is correct
13 Correct 991 ms 70092 KB Output is correct
14 Correct 827 ms 70204 KB Output is correct
15 Correct 826 ms 69944 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 432 KB Output is correct
18 Correct 117 ms 59312 KB Output is correct
19 Correct 154 ms 9164 KB Output is correct
20 Correct 546 ms 65952 KB Output is correct
21 Correct 491 ms 66124 KB Output is correct
22 Correct 381 ms 66168 KB Output is correct
23 Correct 542 ms 66324 KB Output is correct
24 Correct 596 ms 66372 KB Output is correct
25 Incorrect 0 ms 348 KB Output isn't correct
26 Halted 0 ms 0 KB -