제출 #571379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571379		kshitij_sodani	사탕 분배 (IOI21_candies)	C++17	0 / 100	137 ms	49060 KiB

candies

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'

#include "candies.h"
#include <vector>
llo tree[4*200001][4];
llo lazy[4*200001];
//min
//max
//max-min
vector<pair<int,int>> pre[200001];
vector<pair<int,int>> pre2[200001];
void push(int no,int l,int r){
	tree[no][0]+=lazy[no];
	tree[no][1]+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;
}
void update(int no,int l,int r,int aa,int bb,int x){
	push(no,l,r);
	if(l>bb or r<aa or aa>bb){
		return;
	}
	if(aa<=l and r<=bb){
		lazy[no]+=x;
		push(no,l,r);
	}
	else{
		int mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,x);
		update(no*2+2,mid+1,r,aa,bb,x);
		tree[no][0]=min(tree[no*2+1][0],tree[no*2+2][0]);
		tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]);
		tree[no][2]=min(tree[no*2+1][2],tree[no*2+2][2]);
		tree[no][2]=min(tree[no][2],tree[no*2+2][0]-tree[no*2+1][1]);
		tree[no][3]=max(tree[no*2+1][3],tree[no*2+2][3]);
		tree[no][3]=max(tree[no][3],tree[no*2+2][1]-tree[no*2+1][0]);
	}
}
llo query(int no,int l,int r,int aa,int bb){
	push(no,l,r);
	if(r<aa or l>bb or aa>bb){
		return (llo)1e18;
	}
	if(aa<=l and r<=bb){
		return tree[no][0];
	}
	int mid=(l+r)/2;
	return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
   	vector<int> ans;
    int q=l.size();
    for(int i=0;i<q;i++){
    	pre[l[i]].pb({i,v[i]});
    }
    for(int i=0;i<q;i++){
    	pre2[r[i]].pb({i,v[i]});
    }
    llo su=0;
    for(int i=0;i<n;i++){
    	for(auto j:pre[i]){
    		update(0,0,q,j.a+1,q,j.b);
    		su+=j.b;

    	}
    	llo ind=0;
    	if(tree[0][2]<=-c[i]){
    		llo no=0;
    		pair<llo,llo> cur={0,q};
    		llo ma=0;
    		while(cur.a<cur.b){
    			int mid=(cur.a+cur.b)/2;
    			llo ok=0;
    			if(tree[no*2+2][0]-tree[no*2+1][1]<=-c[i]){
    				ok=1;
    			}
    			if(tree[no*2+2][2]<=-c[i]){
    				ok=1;
    			}
    			if(tree[no*2+2][2]-ma<=-c[i]){
    				ok=1;
    			}
    			if(ok==1){
    				ma=max(ma,tree[no*2+1][1]);
    				cur={mid+1,cur.b};
    				no*=2;
    				no+=2;
    				continue;
    			}
    			cur={cur.a,mid};
    			no=no*2+1;
    		}
    		if(tree[no][0]-ma<=-c[i]){
    			ind=cur.a;
    		}
    	}
    	llo ind2=0;
    	if(tree[0][3]>=c[i]){
    		llo no=0;
    		pair<llo,llo> cur={0,q};
    		llo ma=0;
    		while(cur.a<cur.b){
    			/*if(i==2){
    				cout<<cur.a<<","<<cur.b<<endl;
    			}*/
    			/*if(i==1){
    				cout<<cur.a<<","<<cur.b<<":"<<ma<<endl;
    			}*/
    			
    			int mid=(cur.a+cur.b)/2;
    			push(no,cur.a,cur.b);
    			push(no*2+1,cur.a,mid);
    			push(no*2+2,mid+1,cur.b);

    			llo ok=0;
    			if(tree[no*2+2][1]-tree[no*2+1][0]>=c[i]){
    				ok=1;
    			}
    			/*if(i==2){
    				cout<<ok<<','<<endl;
    				cout<<tree[no*2+2][1]-tree[no*2+1][0]<<"::"<<endl;
    			}*/
    			if(tree[no*2+2][3]>=c[i]){
    				ok=1;
    			}
    		/*	if(i==2){
    				cout<<ok<<','<<endl;
    			}*/
    			if(tree[no*2+2][3]-ma>=c[i]){
    				ok=1;
    			}
    			/*if(i==2){
    				cout<<ok<<','<<endl;
    			}*/
    			if(ok==1){
    				ma=min(ma,tree[no*2+1][0]);
    				cur={mid+1,cur.b};

    				no*=2;
    				no+=2;
    				continue;
    			}
    			assert(0==1);
    			cur={cur.a,mid};
    			no=no*2+1;
    		}
    	
    		if(i==2){
    			//cout<<no<<",,"<<endl;
    			//cout<<tree[no][1]<<",,"<<ma<<endl;
    		}
    		if(tree[no][1]-ma>=c[i]){
    			ind2=cur.a;
    		}

    		//cout<<11<<endl;
    	}
    	//cout<<i<<":"<<ind<<":"<<ind2<<endl;
    	assert(ind==0);
    	//ans.pb(min(su,(llo)c[i]));
    	if(ind2>ind){
    		llo ans2=c[i]+su-query(0,0,q,ind2,ind2);
    		ans.pb(ans2);
    	}
    	else{
    		llo ans2=su-query(0,0,q,ind,ind);
    		ans.pb(ans2);
    	}
    
    	for(auto j:pre2[i]){
    		update(0,0,q,j.a+1,q,-j.b);
    		su-=j.b;
    	}
    }


    return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33