Submission #18094

#	Time	Username	Problem	Language	Result	Execution time	Memory
18094		comet	컬러볼 (KOI15_ball)	C++98	25 / 25	222 ms	26496 KiB

ball

#include <cstdio>
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;
typedef vector<int> vec;

int N;
vec a[200010],a_sum[200010];
vec s,sum;

int in[200010],in2[200010];

int query(vec& A,vec& B,int c){
	int id = upper_bound(A.begin(),A.end(),c-1)-A.begin();
	if(id==0)return 0;
	return B[id-1];
}

int main(){
	scanf("%d",&N);
	int x,y;
	s.resize(N);
	sum.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d%d",&x,&y);
		a[x].pb(y);
		s[i]=y;
		in[i]=x,in2[i]=y;
	}

	sort(s.begin(),s.end());
	for(int i=0;i<N;i++){
		sum[i]=s[i];
		if(i)sum[i]+=sum[i-1];
	}
	for(int i=1;i<=200000;i++){
		if(a[i].empty())continue;
		sort(a[i].begin(),a[i].end());
		a_sum[i].resize(a[i].size());
		for(int j=0;j<a[i].size();j++){
			a_sum[i][j]=a[i][j];
			if(j)a_sum[i][j]+=a_sum[i][j-1];
		}
	}

	for(int i=0;i<N;i++){
		printf("%d\n",query(s,sum,in2[i])-query(a[in[i]],a_sum[in[i]],in2[i]));
	}
	return 0;
}

• Subtask 1: 25 / 25