oj.uz

Submission #571355

# Submission time Handle Problem Language Result Execution time Memory
571355 2022-06-01T22:27:14 Z PedroBigMan Distributing Candies (IOI21_candies) C++17
40 / 100
 3859 ms 81336 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 500000000000LL
#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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 4 ms 820 KB Output is correct
5 Correct 14 ms 988 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3373 ms 74876 KB Output is correct
2 Correct 3595 ms 75076 KB Output is correct
3 Correct 3854 ms 74856 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 766 ms 61540 KB Output is correct
3 Correct 1002 ms 19892 KB Output is correct
4 Correct 3859 ms 80692 KB Output is correct
5 Correct 3606 ms 81096 KB Output is correct
6 Correct 3042 ms 81336 KB Output is correct
7 Incorrect 3005 ms 80604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 262 ms 60424 KB Output is correct
4 Correct 873 ms 18964 KB Output is correct
5 Correct 2840 ms 77692 KB Output is correct
6 Correct 2667 ms 78308 KB Output is correct
7 Correct 2394 ms 78884 KB Output is correct
8 Correct 2859 ms 77556 KB Output is correct
9 Correct 3199 ms 79008 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 4 ms 820 KB Output is correct
5 Correct 14 ms 988 KB Output is correct
6 Correct 3373 ms 74876 KB Output is correct
7 Correct 3595 ms 75076 KB Output is correct
8 Correct 3854 ms 74856 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 766 ms 61540 KB Output is correct
11 Correct 1002 ms 19892 KB Output is correct
12 Correct 3859 ms 80692 KB Output is correct
13 Correct 3606 ms 81096 KB Output is correct
14 Correct 3042 ms 81336 KB Output is correct
15 Incorrect 3005 ms 80604 KB Output isn't correct
16 Halted 0 ms 0 KB -