oj.uz

Submission #862126

# Submission time Handle Problem Language Result Execution time Memory
862126 2023-10-17T14:26:26 Z sunwukong123 Distributing Candies (IOI21_candies) C++17
67 / 100
 1160 ms 66948 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 0 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 1000 ms 66948 KB Output is correct
2 Correct 1086 ms 66772 KB Output is correct
3 Correct 1160 ms 66760 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 373 ms 57912 KB Output is correct
3 Correct 205 ms 9140 KB Output is correct
4 Correct 1016 ms 66928 KB Output is correct
5 Correct 986 ms 66792 KB Output is correct
6 Correct 842 ms 66848 KB Output is correct
7 Correct 840 ms 66688 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 348 KB Output is correct
3 Correct 110 ms 57324 KB Output is correct
4 Correct 145 ms 8328 KB Output is correct
5 Correct 535 ms 63300 KB Output is correct
6 Correct 484 ms 63812 KB Output is correct
7 Correct 383 ms 64688 KB Output is correct
8 Correct 542 ms 63644 KB Output is correct
9 Correct 588 ms 64432 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 0 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 1000 ms 66948 KB Output is correct
7 Correct 1086 ms 66772 KB Output is correct
8 Correct 1160 ms 66760 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 373 ms 57912 KB Output is correct
11 Correct 205 ms 9140 KB Output is correct
12 Correct 1016 ms 66928 KB Output is correct
13 Correct 986 ms 66792 KB Output is correct
14 Correct 842 ms 66848 KB Output is correct
15 Correct 840 ms 66688 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 110 ms 57324 KB Output is correct
19 Correct 145 ms 8328 KB Output is correct
20 Correct 535 ms 63300 KB Output is correct
21 Correct 484 ms 63812 KB Output is correct
22 Correct 383 ms 64688 KB Output is correct
23 Correct 542 ms 63644 KB Output is correct
24 Correct 588 ms 64432 KB Output is correct
25 Incorrect 0 ms 348 KB Output isn't correct
26 Halted 0 ms 0 KB -