oj.uz

Submission #862128

# Submission time Handle Problem Language Result Execution time Memory
862128 2023-10-17T14:27:14 Z sunwukong123 Distributing Candies (IOI21_candies) C++17
67 / 100
 1310 ms 70640 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 || 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 1 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 856 KB Output is correct
5 Correct 4 ms 956 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 66836 KB Output is correct
2 Correct 1275 ms 66848 KB Output is correct
3 Correct 1310 ms 69084 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 390 ms 59716 KB Output is correct
3 Correct 218 ms 10744 KB Output is correct
4 Correct 1115 ms 70220 KB Output is correct
5 Correct 1062 ms 70516 KB Output is correct
6 Correct 921 ms 70640 KB Output is correct
7 Correct 931 ms 70120 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 117 ms 58964 KB Output is correct
4 Correct 160 ms 9160 KB Output is correct
5 Correct 570 ms 66604 KB Output is correct
6 Correct 540 ms 66464 KB Output is correct
7 Correct 389 ms 66088 KB Output is correct
8 Correct 571 ms 66044 KB Output is correct
9 Correct 590 ms 66120 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 856 KB Output is correct
5 Correct 4 ms 956 KB Output is correct
6 Correct 1020 ms 66836 KB Output is correct
7 Correct 1275 ms 66848 KB Output is correct
8 Correct 1310 ms 69084 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 390 ms 59716 KB Output is correct
11 Correct 218 ms 10744 KB Output is correct
12 Correct 1115 ms 70220 KB Output is correct
13 Correct 1062 ms 70516 KB Output is correct
14 Correct 921 ms 70640 KB Output is correct
15 Correct 931 ms 70120 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 117 ms 58964 KB Output is correct
19 Correct 160 ms 9160 KB Output is correct
20 Correct 570 ms 66604 KB Output is correct
21 Correct 540 ms 66464 KB Output is correct
22 Correct 389 ms 66088 KB Output is correct
23 Correct 571 ms 66044 KB Output is correct
24 Correct 590 ms 66120 KB Output is correct
25 Incorrect 0 ms 348 KB Output isn't correct
26 Halted 0 ms 0 KB -