Submission #386807

#	Time	Username	Problem	Language	Result	Execution time	Memory
386807		alishahali1382	Teams (IOI15_teams)	C++14	100 / 100	1371 ms	219780 KiB

teams

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

typedef long long ll;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<"="<<x<<", "<<y<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define all(x) x.begin(), x.end()
#define pb push_back

const int MAXN=500010, SEGSZ=20000010;

int n, x, y;
int A[MAXN], B[MAXN], root[MAXN];
int seg[SEGSZ], L[SEGSZ], R[SEGSZ], ts;
priority_queue<int, vector<int>, greater<int>> pq;

int Add(int id, int tl, int tr, int pos, int val=1){
	if (pos<tl || tr<=pos) return id;
	int res=++ts;
	if (tr-tl==1){
		seg[res]=seg[id]+val;
		return res;
	}
	int mid=(tl+tr)>>1;
	L[res]=Add(L[id], tl, mid, pos, val);
	R[res]=Add(R[id], mid, tr, pos, val);
	seg[res]=seg[L[res]]+seg[R[res]];
	return res;
}
int Get(int idl, int idr, int tl, int tr, int l, int r){
	if (r<=tl || tr<=l) return 0;
	if (l<=tl && tr<=r) return seg[idr]-seg[idl];
	int mid=(tl+tr)>>1;
	return Get(L[idl], L[idr], tl, mid, l, r) + Get(R[idl], R[idr], mid, tr, l, r);
}
void init(int nn, int AA[], int BB[]){
	n=nn;
	vector<pii> vec;
	for (int i=0; i<n; i++) vec.pb({AA[i], BB[i]});
	sort(all(vec));
	for (int i=0; i<n; i++) A[i+1]=vec[i].first, B[i+1]=vec[i].second;
	int j=1;
	for (int i=1; i<=n; i++){
		root[i]=root[i-1];
		while (A[j]==i) root[i]=Add(root[i], 1, n+1, B[j++]);
	}
}
pii BS(int id1, int id2, int tl, int tr, int l, int r, int val){
	// cerr<<"BS "<<tl<<" "<<tr<<"  "<<l<<" "<<r<<"  "<<val<<"\n";
	if (r<=tl || tr<=l) return {tr, 0};
	if (l<=tl && tr<=r && seg[id1]-seg[id2]<val) return {tr, seg[id1]-seg[id2]};
	if (tr-tl==1) return {tl, 0};
	int mid=(tl+tr)>>1;
	pii res=BS(L[id1], L[id2], tl, mid, l, r, val);
	if (res.first<mid) return res;
	pii p=BS(R[id1], R[id2], mid, tr, l, r, val-res.second);
	return {p.first, p.second+res.second};
}
int Copy(int id1, int id2, int tl, int tr, int l, int r){ // set seg[id1][l...r-1] = seg[id2][l...r-1]
	if (r<=tl || tr<=l) return id1;
	if (l<=tl && tr<=r) return id2;
	int res=++ts, mid=(tl+tr)>>1;
	L[res]=Copy(L[id1], L[id2], tl, mid, l, r);
	R[res]=Copy(R[id1], R[id2], mid, tr, l, r);
	seg[res]=seg[L[res]]+seg[R[res]];
	return res;
}
int can(int m, int C[]){
	sort(C, C+m);
	int used=0;
	for (int i=0; i<m; i++){
		int k=C[i];
		pii p=BS(root[k], used, 1, n+1, k, n+1, k);
		// debugp(p)
		if (p.first==n+1) return 0;
		used=Copy(used, root[k], 1, n+1, 1, p.first);
		used=Add(used, 1, n+1, p.first, k-p.second);
	}
	return 1;
}

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