oj.uz

Submission #571356

# Submission time Handle Problem Language Result Execution time Memory
571356 2022-06-01T22:28:48 Z PedroBigMan Distributing Candies (IOI21_candies) C++17
100 / 100
 3817 ms 80248 KB 
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "candies.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000000000LL
#define EPS 0.00000001
#define pi 3.14159
#define VV(vvvv,NNNN,xxxx); REP(i,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

class ST_max
{	
    public:
    ll N;
    
    class SV //seg value
    {
        public:
        ll a; ll ind;
        SV() {a=-INF;}
        SV(ll x) {a=x;}
        
        SV operator & (SV X) 
		{
			SV ANS(max(a,X.a)); 
			if(a>X.a) {ANS.ind=ind;} else {ANS.ind=X.ind;}
			return ANS;
		}
    };
      
    class LV //lazy value
    {
        public:
        ll a;
        LV() {a=0LL;}
        LV(ll x) {a=x;}
        
        LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
    };
    
    SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
    {
        SV X(p[c].a+lazy[c].a); X.ind=p[c].ind;
        return X;
    }
    
    SV neuts; LV neutl;
    
    vector<SV> p;
    vector<LV> lazy;
    vector<pl> range;
    
    ST_max() {N=0LL;}
    ST_max(vector<ll> arr)
    {
        N = (ll) 1<<(ll) ceil(log2(arr.size()));
        REP(i,0,2*N) {range.pb(mp(0LL,0LL));}
        REP(i,0,N) {p.pb(neuts);}
        REP(i,0,arr.size()) {SV X(arr[i]); X.ind=i; p.pb(X); range[i+N]=mp(i,i);}
        REP(i,arr.size(),N) {p.pb(neuts); p.back().ind=i; range[i+N]=mp(i,i);}
        ll cur = N-1;
        while(cur>0)
        {
            p[cur]=p[2*cur]&p[2*cur+1];
            range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss);
            cur--;
        }
        REP(i,0,2*N) {lazy.pb(neutl);}
    }
    
    void prop(ll c) //how lazy values propagate
    {
        lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1];
        lazy[c]=neutl;
    }
    
    SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return upval(c);}
        prop(c);
		p[c]=upval(2*c)&upval(2*c+1);
        SV ans = query(a,b,2*c)&query(a,b,2*c+1);
        return ans;
    }
    
    void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return ;}
        if(x>=a && y<=b) 
        {
            lazy[c]=s&lazy[c]; 
            return;
        }
		prop(c);
        update(s,a,b,2*c); update(s,a,b,2*c+1);
        p[c]=upval(2*c)&upval(2*c+1);
    }
};

class ST_min
{	
    public:
    ll N;
    
    class SV //seg value
    {
        public:
        ll a; ll ind;
        SV() {a=INF;}
        SV(ll x) {a=x;}
        
        SV operator & (SV X) 
		{
			SV ANS(min(a,X.a)); 
			if(a<X.a) {ANS.ind=ind;} else {ANS.ind=X.ind;}
			return ANS;
		}
    };
      
    class LV //lazy value
    {
        public:
        ll a;
        LV() {a=0LL;}
        LV(ll x) {a=x;}
        
        LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
    };
    
    SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
    {
        SV X(p[c].a+lazy[c].a); X.ind=p[c].ind;
        return X;
    }
    
    SV neuts; LV neutl;
    
    vector<SV> p;
    vector<LV> lazy;
    vector<pl> range;
    
    ST_min() {N=0LL;}
    ST_min(vector<ll> arr)
    {
        N = (ll) 1<<(ll) ceil(log2(arr.size()));
        REP(i,0,2*N) {range.pb(mp(0LL,0LL));}
        REP(i,0,N) {p.pb(neuts);}
        REP(i,0,arr.size()) {SV X(arr[i]); X.ind=i; p.pb(X); range[i+N]=mp(i,i);}
        REP(i,arr.size(),N) {p.pb(neuts); p.back().ind=i; range[i+N]=mp(i,i);}
        ll cur = N-1;
        while(cur>0)
        {
            p[cur]=p[2*cur]&p[2*cur+1];
            range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss);
            cur--;
        }
        REP(i,0,2*N) {lazy.pb(neutl);}
    }
    
    void prop(ll c) //how lazy values propagate
    {
        lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1];
        lazy[c]=neutl;
    }
    
    SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return upval(c);}
        prop(c);
		p[c]=upval(2*c)&upval(2*c+1);
        SV ans = query(a,b,2*c)&query(a,b,2*c+1);
        return ans;
    }
    
    void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return ;}
        if(x>=a && y<=b) 
        {
            lazy[c]=s&lazy[c]; 
            return;
        }
		prop(c);
        update(s,a,b,2*c); update(s,a,b,2*c+1);
        p[c]=upval(2*c)&upval(2*c+1);
    }
};

vector<int> distribute_candies(vector<int> cc, vector<int> lll, vector<int> rrr, vector<int> vv) 
{
   	ll N,Q; vector<ll> C,L,R,V;
	N=cc.size(); REP(i,0,N) {C.pb((ll) cc[i]);}
	Q=lll.size(); L.pb(0); R.pb(N-1); V.pb(-INF/10); REP(i,0,Q) {L.pb((ll) lll[i]); R.pb((ll) rrr[i]); V.pb((ll) vv[i]);} Q++;
	vector<ll> xx; VV(xx,Q,0LL); ST_min PS_min(xx); ST_max PS_max(xx);
	vector<vector<ll> > pos_beg,pos_end; VV(pos_beg,N+1,{}); VV(pos_end,N+1,{});
	REP(i,0,Q) {pos_beg[L[i]].pb(i); pos_end[R[i]+1].pb(i);}
	vector<int> ans;
	REP(i,0,N)
	{
		REP(j,0,pos_beg[i].size()) {ll ind = pos_beg[i][j]; PS_min.update(V[ind],ind,Q-1); PS_max.update(V[ind],ind,Q-1);}
		REP(j,0,pos_end[i].size()) {ll ind = pos_end[i][j]; PS_min.update(-V[ind],ind,Q-1); PS_max.update(-V[ind],ind,Q-1);}
		ll lo=0; ll hi=Q-1;
		ll mid, max_ps, min_ps;
		while(lo<hi)
		{
			mid = (lo+hi+1)/2;
			if(mid==0) {max_ps=max(0LL,PS_max.query(0,Q-1).a); min_ps=min(0LL,PS_min.query(0,Q-1).a);}
			else {max_ps=PS_max.query(mid-1,Q-1).a; min_ps=PS_min.query(mid-1,Q-1).a;}
			if(max_ps-min_ps>=C[i]) {lo=mid;} else {hi=mid-1;}
		}
		ll ind_max=0, ind_min=0;
		if(lo==0) {if(PS_max.query(0,Q-1).a>=0) {ind_max=PS_max.query(0,Q-1).ind;} if(PS_min.query(0,Q-1).a<=0) {ind_min=PS_min.query(0,Q-1).ind;}}
		else {ind_max=PS_max.query(lo-1,Q-1).ind; ind_min=PS_min.query(lo-1,Q-1).ind;}
		ll start; bool up;
		if(ind_max>ind_min) {start=ind_max+1; up=true;} else {start=ind_min+1; up=false;}
		ll acc = PS_max.query(Q-1,Q-1).a-PS_max.query(start-1,start-1).a;
		ll curans; if(up) {curans=C[i]+acc;} else {curans=acc;}
		ans.pb((int) curans);
		
	}
	return ans;
}

Compilation message

candies.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
candies.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 4 ms 824 KB Output is correct
5 Correct 13 ms 980 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3366 ms 75180 KB Output is correct
2 Correct 3626 ms 75196 KB Output is correct
3 Correct 3694 ms 75184 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 762 ms 59176 KB Output is correct
3 Correct 1012 ms 18484 KB Output is correct
4 Correct 3817 ms 75148 KB Output is correct
5 Correct 3606 ms 75144 KB Output is correct
6 Correct 3064 ms 75164 KB Output is correct
7 Correct 3062 ms 75264 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 257 ms 60640 KB Output is correct
4 Correct 870 ms 18552 KB Output is correct
5 Correct 2839 ms 74756 KB Output is correct
6 Correct 2696 ms 74852 KB Output is correct
7 Correct 2393 ms 74636 KB Output is correct
8 Correct 2775 ms 74640 KB Output is correct
9 Correct 2993 ms 74696 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 4 ms 824 KB Output is correct
5 Correct 13 ms 980 KB Output is correct
6 Correct 3366 ms 75180 KB Output is correct
7 Correct 3626 ms 75196 KB Output is correct
8 Correct 3694 ms 75184 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 762 ms 59176 KB Output is correct
11 Correct 1012 ms 18484 KB Output is correct
12 Correct 3817 ms 75148 KB Output is correct
13 Correct 3606 ms 75144 KB Output is correct
14 Correct 3064 ms 75164 KB Output is correct
15 Correct 3062 ms 75264 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 257 ms 60640 KB Output is correct
19 Correct 870 ms 18552 KB Output is correct
20 Correct 2839 ms 74756 KB Output is correct
21 Correct 2696 ms 74852 KB Output is correct
22 Correct 2393 ms 74636 KB Output is correct
23 Correct 2775 ms 74640 KB Output is correct
24 Correct 2993 ms 74696 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 910 ms 18964 KB Output is correct
27 Correct 758 ms 61144 KB Output is correct
28 Correct 3530 ms 79076 KB Output is correct
29 Correct 3487 ms 79568 KB Output is correct
30 Correct 3422 ms 79772 KB Output is correct
31 Correct 3156 ms 79960 KB Output is correct
32 Correct 3099 ms 80248 KB Output is correct