oj.uz

답안 #435495

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
435495 2021-06-23T11:29:49 Z kshitij_sodani 사탕 분배 (IOI21_candies) C++17
29 / 100
 2086 ms 27212 KB 
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;

#include "candies.h"

#include <vector>
llo cur[200001];
llo tree[4*200001];
llo tree2[4*200001];
void update(llo no,llo l,llo r,llo i,llo j){
	if(l==r){
		tree[no]=j;
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			update(no*2+1,l,mid,i,j);
		}
		else{
			update(no*2+2,mid+1,r,i,j);
		}	
		tree[no]=max(tree[no*2+1],tree[no*2+2]);

	}
}


void update2(llo no,llo l,llo r,llo i,llo j){
	if(l==r){
		tree2[no]=j;
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			update2(no*2+1,l,mid,i,j);
		}
		else{
			update2(no*2+2,mid+1,r,i,j);
		}	
		tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);

	}
}
llo query2(llo no,llo l,llo r,llo aa,llo bb){
	if(r<aa or l>bb){
		return -1;
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	llo mid=(l+r)/2;
	return max(query2(no*2+1,l,mid,aa,bb),query2(no*2+2,mid+1,r,aa,bb));
}
llo query3(llo no,llo l,llo r,llo aa,llo bb){
	if(r<aa or l>bb){
		return -1;
	}
	if(aa<=l and r<=bb){
		return tree2[no];
	}
	llo mid=(l+r)/2;
	return max(query3(no*2+1,l,mid,aa,bb),query3(no*2+2,mid+1,r,aa,bb));
}

llo val2[2000001];
llo pre[2000001];
llo cot=-1;
vector<pair<llo,llo>> ss;
llo n;
llo query(llo ind){
	llo x=query2(0,0,n-1,ind,n-1);
	llo y=query3(0,0,n-1,ind,n-1);
	llo z;
	if(x<=y){
		z=0;
	}
	else{
		z=ss[ind].a;
	}
	//cout<<ind<<":"<<x<<":"<<y<<":"<<z<<endl;
	z+=pre[cot]-pre[max(x,y)+1];
	return z;
}

//llo lazy2[]
/*void u(llo i,llo j){
	while(i<=200000){
		tree[i]+=j;
		i+=(i&-i);
	}
}
llo ss(llo i){
	llo su=0;
	while(i>0){
		su+=tree[i];
		i-=(i&-i);
	}
	return su;
}*/

std::vector<int> distribute_candies(vector<int> it,vector<int> ll,
                                    vector<int> rr,vector<int> aa) {
    	


    pre[0]=0;
    for(llo i=1;i<=aa.size();i++){
    	pre[i]=pre[i-1]+aa[i-1];
    }
   
   /*	for(int i=0;i<=aa.size();i++){
   		cout<<pre[i]<<":";
   	}
   	cout<<endl;*/
	n=it.size();
	llo q=ll.size();
	for(llo i=0;i<n;i++){
		cur[i]=0;
	}
	for(llo i=0;i<4*n;i++){
		tree[i]=-1;
	}
	for(llo i=0;i<4*n;i++){
		tree2[i]=-1;
	}
	


	for(llo i=0;i<n;i++){
		ss.pb({it[i],i});
	}
	sort(ss.begin(),ss.end());



	for(llo i=0;i<q;i++){
		cot=i;
		/*for(int j=0;j<n;j++){
			cout<<query(j)<<":";
		}
		cout<<endl;*/
		if(aa[i]>0){
			llo low=-1;
			for(llo j=19;j>=0;j--){
				if(low+(1<<j)<n){
					llo ind=low+(1<<j);
					llo xx=query(ind);
					//cout<<low<<":"<<xx<<endl;
					if(xx+aa[i]>=ss[ind].a){
						low=ind;
					}
				}
			}
			/*if(low+1<n){
				update(0,0,n-1,low+1,n,aa[i]);
			}*/
			if(low>=0){
				//set to max val
				update(0,0,n-1,low,i);
			}
			//cout<<low<<":"<<endl;
		}
		else{
			llo low=-1;
			for(llo j=19;j>=0;j--){
				if(low+(1<<j)<n){
					llo ind=low+(1<<j);
					llo xx=query(ind);
					if(xx+aa[i]<0){
						low=ind;
					}
				}
			}
		/*	if(low+1<n){
				update(0,0,n-1,low+1,n,aa[i]);
			}*/
			if(low>=0){
				//set to 0
				//set to max val
				update2(0,0,n-1,low,i);
			}
			//cout<<low<<":"<<endl;
		}


		//u(ll[i]+1,aa[i]);
		//u(rr[i]+2,-aa[i]);
		/*for(llo j=ll[i];j<=rr[i];j++){
			cur[j]+=aa[i];
			cur[j]=max(cur[j],0);
			cur[j]=min(cur[j],it[j]);
		}*/
	}
	vector<int> ans;
	for(llo i=0;i<n;i++){
		ans.pb(0);
	}
	cot=q;
	for(llo i=0;i<n;i++){
		ans[ss[i].b]=query(i);
		//ans.pb((llo)min((llo)it[i],ss(i+1)));
		//cout<<ss(i+1)<<":";
	}
	//cout<<endl;










    return ans;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:111:18: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(llo i=1;i<=aa.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 740 ms 27212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 605 ms 6816 KB Output is correct
4 Correct 195 ms 21148 KB Output is correct
5 Correct 1990 ms 27180 KB Output is correct
6 Correct 2027 ms 27164 KB Output is correct
7 Correct 1931 ms 27164 KB Output is correct
8 Correct 2086 ms 27184 KB Output is correct
9 Correct 1629 ms 27168 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -