Submission #1293621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293621		goulthen	Teams (IOI15_teams)	C++20	0 / 100	4091 ms	13404 KiB

teams

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

#define rep(i,a,b) for (int i = a; i <= b; i++)
#define pii pair<int,int>
#define fi first
#define se second

const int MAXN = 5e5+10; // ONLY FOR LOCAL
pii a[MAXN];
int n, cnt[MAXN];
bool tag = 1;

struct Seg3 {
	int seg[4*MAXN];

	void update(int ti, int x, int i = 1, int l = 1, int r = n) {
		if(l==r && ti == l) {
			seg[i] += x;
			return;
		}

		int mid = (l+r)/2;
		if(ti<= mid) update(ti, x, 2*i, l, mid);
		else update(ti, x, 2*i+1, mid +1, r);
	}
	int find(int i, int l, int r) {
		if(l==r) return l;
		int mid = (l+r)/2;

		if(seg[2*i] > 0) return find(2*i,l,mid);
		else return find(2*i+1,mid+1,r);
	}

	int query(int tl, int tr, int i = 1, int l = 1, int r = n) {
		if(tr < l || r < tl) return 0LL;
		if (tl <= l && tr >= r) {
			if(tag) {
				tag = 0;
				return find(i,l,r);
			}
			return 0;
		}
		int mid = (l+r)/2;

		return query(tl,tr,2*i,l,mid) + query(tl,tr,2*i+1,mid+1,r);
	}
};
Seg3 seg;

void init(int N, int A[], int B[]) {
	n = N;
	rep(i,0,N-1) a[i+1] = {B[i],A[i]};
	sort(a+1, a+n+1);
}

int can(int M, int K[]) {
	int s = 0;

	rep(i,0,M-1) seg.update(K[i],K[i]), s+=K[i], cnt[K[i]]+=K[i];

	rep(i,1,n) {
		tag=1;
		int k = seg.query(a[i].se, a[i].fi);
		//cout << a[i].se << ' ' << a[i].fi << ' ' << k << '\n';
		if(k!=0) {

			cnt[k]--;
			s--;
			seg.update(k,-1);
		}
	}

	rep(i,0,M-1) {
		if(cnt[K[i]] == 0) continue;
		seg.update(K[i],-cnt[K[i]]);
		cnt[K[i]] = 0;
	}
	return s==0;
}

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