Submission #18094

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
18094	2016-01-20T06:04:29 Z	comet	컬러볼 (KOI15_ball)	C++	25 / 25	222 ms	26496 KB

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.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	26496 KB	Output is correct
2	Correct	209 ms	26496 KB	Output is correct
3	Correct	189 ms	26496 KB	Output is correct
4	Correct	211 ms	26496 KB	Output is correct
5	Correct	222 ms	26496 KB	Output is correct
6	Correct	9 ms	12652 KB	Output is correct
7	Correct	8 ms	12652 KB	Output is correct
8	Correct	4 ms	12652 KB	Output is correct
9	Correct	5 ms	12652 KB	Output is correct
10	Correct	6 ms	12652 KB	Output is correct
11	Correct	190 ms	15796 KB	Output is correct
12	Correct	192 ms	15892 KB	Output is correct
13	Correct	189 ms	15800 KB	Output is correct
14	Correct	181 ms	15872 KB	Output is correct
15	Correct	167 ms	15900 KB	Output is correct
16	Correct	161 ms	19736 KB	Output is correct
17	Correct	163 ms	20668 KB	Output is correct
18	Correct	205 ms	20476 KB	Output is correct
19	Correct	214 ms	20384 KB	Output is correct
20	Correct	211 ms	20952 KB	Output is correct