Submission #831413

#TimeUsernameProblemLanguageResultExecution timeMemory
831413waldiTeams (IOI15_teams)C++17
34 / 100
4080 ms45396 KiB
#include<bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
using namespace std;

int n;
vector<vector<int>> kub;
void init(int nn, int a[], int b[]){
	n = nn;
	kub.resize(n+1);
	REP(i, n) kub[a[i]].emplace_back(b[i]);
}

int can(int m, int k[]){
	vector<int> wym(n+1, 0);
	REP(i, m) wym[k[i]] += k[i];
	// wym ma 2sqrt(n) niezerowych wartosci
	
	multiset<int> s;
	FOR(i, 1, n){
		for(int x : kub[i]) s.emplace(x);
		while(s.size() && *s.begin() < i) s.erase(s.begin());
		
		for(; wym[i]; --wym[i]){
			if(s.empty()) return 0;
			s.erase(s.begin());
		}
	}
	return 1;
}

#ifdef LOCAL
#define maxn 1000
int main(){
	int nn, a[maxn], b[maxn];
	scanf("%d", &nn);
	REP(i, nn) scanf("%d%d", &a[i], &b[i]);
	init(nn, a, b);
	
	int q;
	scanf("%d", &q);
	while(q--){
		int m, k[maxn];
		scanf("%d", &m);
		REP(i, m) scanf("%d", &k[i]);
		int wyn = can(m, k);
		printf("%d\n", wyn);
	}
}
#endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...