Submission #1261252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261252		kl0989e	Teams (IOI15_teams)	C++20	0 / 100	50 ms	14916 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

int n;
vi pbeg;
vi pend;

void init(int _n, int a[], int b[]) {
	n=_n;
	pbeg.resize(n+1,0);
	pend.resize(n+1,0);
	for (int i=0; i<n; i++) {
		pbeg[a[i]]++;
		pend[b[i]]++;
	}
	for (int i=0; i<n; i++) {
		pbeg[i+1]+=pbeg[i];
		pend[i+1]+=pend[i];
	}
}

int can(int m, int k[]) {
	sort(k,k+m);
	vector<pl> kk={{k[0],k[0]}};
	vi sub={0};
	for (int i=1; i<m; i++) {
		if (k[i]==kk.back().fi) {
			kk.back().se+=k[i];
		}
		else {
			kk.pb({k[i],k[i]});
			sub.pb(0);
		}
	}
	int prv=0;
	int pt=1;
	int cnt=0;
	for (int i=0; i<kk.size(); i++) {
		cnt+=pbeg[kk[i].fi]-pbeg[prv];
		cnt-=pend[kk[i].fi-1]-pend[max(prv-1,0)]-sub[i];
		if (cnt<kk[i].se) {
			return 0;
		}
		cnt-=kk[i].se;
		pt=max(pt,i+1);
		prv=kk[i].fi;
		while (kk[i].se && pt<kk.size()) {
			ll v=min(kk[i].se,1ll*pend[kk[pt].fi-1]-pend[max(kk[pt-1].fi-1,0ll)]-sub[pt]);
			sub[pt]+=v;
			kk[i].se-=v;
			if (sub[pt]==pend[kk[pt].fi-1]-pend[max(kk[pt-1].fi-1,0ll)]) {
				pt++;
			}
		}
	}
	return 1;
}

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