Submission #418374

#	Time	Username	Problem	Language	Result	Execution time	Memory
418374		vanic	Teams (IOI15_teams)	C++14	34 / 100	4077 ms	26020 KiB

teams

#include "teams.h"
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

const int maxn=5e5+5;

priority_queue < int, vector < int >, greater < int > > q;
vector < int > sw[maxn];
int n;

void init(int x, int a[], int b[]){
	n=x;
	for(int i=0; i<n; i++){
		sw[a[i]].push_back(b[i]+1);
	}
}

int can(int m, int k[]){
	sort(k, k+m);
	int pos=0;
	for(int i=0; i<=n; i++){
		for(int j=0; j<(int)sw[i].size(); j++){
			q.push(sw[i][j]);
		}
		while(!q.empty() && q.top()==i){
			q.pop();
		}
//		cout <<  "sz " << q.size() << endl;
		while(pos<m && k[pos]==i){
			if((int)q.size()<i){
				while(!q.empty()){
					q.pop();
				}
				return 0;
			}
			for(int j=0; j<i; j++){
				q.pop();
			}
			pos++;
		}
	}
	while(!q.empty()){
		q.pop();
	}
	return 1;
}

/*
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	int a[n], b[n];
	for(int i=0; i<n; i++){
		cin >> a[i] >> b[i];
	}
	init(n, a, b);
	int q;
	cin >> q;
	for(int i=0; i<q; i++){
		int m;
		cin >> m;
		int c[m];
		for(int j=0; j<m; j++){
			cin >> c[j];
		}
		cout << can(m, c) << '\n';
	}
	return 0;
}
*/

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23