Submission #1311650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311650		PlayVoltz	Teams (IOI15_teams)	C++20	0 / 100	436 ms	156472 KiB

teams

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

#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n;
vector<vector<int> > vect;

struct node{
	int s, e, m;
	vector<int> val;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if (s!=e){
			l = new node(s, m);
			r = new node(m+1, e);
			merge(l->val.begin(), l->val.end(), r->val.begin(), r->val.end(), back_inserter(val));
		}
		else val=vect[s], sort(val.begin(), val.end());
	}
	int query(int left, int right, int v){
		if (left>right)return 0;
		if (s==left && e==right)return (upper_bound(val.begin(), val.end(), v)-val.begin());
		if (right<=m)return l->query(left, right, v);
		else if (left>m)return r->query(left, right, v);
		else return l->query(left, m, v)+r->query(m+1, right, v);
	}
}*st;

void init(int N, int A[], int B[]){
	n=N;
	vect.resize(n+1);
	for (int i=0; i<n; ++i)vect[A[i]].pb(B[i]);
	st = new node(1, n);
}

int can(int m, int ord[]){
	sort(ord, ord+m);
	int extra=0;
	for (int i=0, prev=0; i<m; ++i){
		if (i!=m-1){
			prev=max(prev, ord[i]-1);
			int low=prev, high=n+1, res=0;
			while (low+1<high){
				int mid=(low+high)/2;
				if (st->query(1, ord[i], mid)-st->query(1, ord[i], prev)<ord[i]+extra)low=mid, res=st->query(1, ord[i], mid)-st->query(1, ord[i], prev);
				else high=mid;
			}
			if (low==n)return 0;
			extra=extra+ord[i]-res;
			if (low+1<ord[i+1])extra=max(0, extra-st->query(1, ord[i], ord[i+1])+st->query(1, ord[i], low+1));
			prev=max(prev, low);
		}
		else{
			if (st->query(1, ord[i], n)-st->query(1, ord[i], prev)<ord[i]+extra)return 0;
		}
	}
	return 1;
}

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