Submission #128138

#	Time	Username	Problem	Language	Result	Execution time	Memory
128138		Sorting	Teams (IOI15_teams)	C++14	34 / 100	4051 ms	24404 KiB

teams

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 7;

int n;
int *a, *b;

multiset<int> st;
vector<pair<int, int> > v;

void init(int _n, int *_a, int *_b){
	n = _n;
	a = _a;
	b = _b;

	for(int i = 0; i < n; i++){
		v.push_back({a[i], i + 1});
		v.push_back({b[i] + 1, -i - 1});
	}

	sort(v.begin(), v.end());
}

bool boo[N];

bool can(int m, int *k){
	for(int i = 0; i < n; i++){
		boo[i] = false;
	}

	sort(k, k + m);

	int j = 0;

	st.clear();

	for(int i = 0; i < (int)v.size(); i++){
		pair<int, int> p = v[i];

		int idx;

		if(p.second > 0){
			idx = p.second - 1;
			boo[idx] = true;
			st.insert(b[idx]);
		}
		else{
			idx = -p.second - 1;
			if(boo[idx]){
				st.erase(b[idx]);
				boo[idx] = false;
			}
		}

		if(i == (int)v.size() - 1 || p.first != v[i + 1].first){
			while(j < m && k[j] >= p.first && (i == (int)v.size() - 1 || k[j] < v[i + 1].first)){
				if(st.empty()){
					return 0;
				}

				if((int)st.size() < k[j]){
					return 0;
				}

				for(int r = 0; r < k[j]; r++){
					boo[*st.begin()] = false;
					st.erase(st.begin());
				}
				j++;
			}
		}
	}

	return 1;
}

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