oj.uz

Submission #862062

# Submission time Handle Problem Language Result Execution time Memory
862062 2023-10-17T13:12:43 Z sunwukong123 Distributing Candies (IOI21_candies) C++17
0 / 100
 595 ms 38540 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
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,val,mn,mx;
    node *l, *r;
    node(int _s, int _e){
        s=_s;e=_e;m=(s+e)/2;
        val=mx=mn=0;
        if(s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    void set(int x, int nval){
        if(s==e){
            val+=nval;
            mx=mn=val;
            return;
        }
        if(x>m)r->set(x,nval);
        else l->set(x,nval);
        val=l->val+r->val;
        mn=min(r->mn,r->val+l->mn);
        mx=max(r->mx,r->val+l->mx);
    }
    pi query_min(int x){
        if(s==e){
            return {s,mn};
        }
        if(r->mn<=x)return r->query_min(x);
        else return l->query_min(x);

    }
    pi query_max(int x){
        if(s==e){
            return {s,mx};
        }
        if(r->mx>=x)return r->query_max(x);
        else return l->query_max(x);
    }
    int query(int x, int y){
        if(s==x&&e==y)return val;
        if(x>m)return r->query(x,y);
        else if(y<=m)return l->query(x,y);
        else return l->query(x,m)+r->query(m+1,y);
    }

}*seg;

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> 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<int>res;
    for(int i=0;i<=n-1;i++){
        //debug(i);
        for(auto x:A[i]){
            //debug(x.first,x.second);
            seg->set(x.second,x.first);
        }
        //debug(i);

        int lo=0,hi=c[i]+1;
        while(lo<hi-1){
            int mi=(lo+hi)/2;

            pi MX=seg->query_max(c[i]-mi);
            pi MN=seg->query_min(-c[i]);
            //debug(c[i]-mi,c[i],mi,MX.first,MN.first);
            if(MN.first >= MX.first){
                int sum=0;
                if(MN.first!=Q+3)sum=seg->query(MN.first+1,Q+3);
                if(sum>=mi){
                    lo=mi;
                } else{
                    hi=mi;
                }
            } else{
                int sum=c[i];
                if(MX.first!=Q+3)sum=c[i]+seg->query(MX.first+1,Q+3);
                if(sum>=mi){
                    lo=mi;
                } else {
                    hi=mi;
                }
            }
        }
        res.push_back(lo);
    }
    return res;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 595 ms 38540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -