Submission #831658

#	Time	Username	Problem	Language	Result	Execution time	Memory
831658		qin	Teams (IOI15_teams)	C++14	34 / 100	4043 ms	47332 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
struct st{
		int a, b;
		st(){}
		st(int A, int B) : a(A), b(B) {}
		bool operator <(const st &x) const{return b == x.b ? a < x.a : b < x.b;}
};
int base = 1;
struct seg{
		vector<int> t;
		void init(int n){
				while(base < n) base <<= 1;
				t.resize(base<<1);
		} void update(int i, int w){
				i += base-1; t[i] = w;
				for(i>>=1; i; i>>=1) t[i] = t[i<<1] + t[i<<1|1];
		} int Find(int i, int pocz, int kon){
				if(pocz == kon) return pocz;
				int ret = 0;
				if(t[i<<1]) ret = Find(i<<1, pocz, (pocz+kon)>>1);
				else ret = Find(i<<1|1, ((pocz+kon)>>1)+1, kon);
				return ret;
		} int findsmallest(){
				if(!t[1]) return 0;
				else return Find(1, 1, base);
		}
};
vector<vector<st>> v;
int n;
int can(int m, int T[]){
		vector<int> t(m);
		for(int i = 0; i < m; ++i) t[i] = T[i];
		int suma = 0;
		for(int i = 0; i < m; ++i) suma += t[i];
		if(suma > n) return 0;
		seg seg;
		seg.init(n);
		int it = 0, tmp;
		sort(t.begin(), t.end());
		bool b = 1;
		for(int i = 1; i <= n; ++i){
				for(st u : v[i]) seg.update(u.a, u.b);
				while(it != m && t[it] == i){
						for(int j = 1; j <= i; ++j){
								if(!seg.t[1]) { b = 0; break; }
								tmp = seg.findsmallest();
								seg.update(tmp, 0);
						} ++it;
				}
		} return b;
}
void init(int N, int A[], int B[]){
		n = N;
		vector<int> a(n+1), b(n+1);
		vector<st> t(n);
		for(int i = 1; i <= n; ++i) a[i] = A[i-1];
		for(int i = 1; i <= n; ++i) b[i] = B[i-1], t[i-1] = st(a[i], b[i]);
		sort(t.begin(), t.end());
		v.resize(n+2);
		for(int i = 0; i < n; ++i) v[t[i].a].emplace_back(i+1, 1), v[t[i].b+1].emplace_back(i+1, 0);
}

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