제출 #1263115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263115		kl0989e	팀들 (IOI15_teams)	C++20	100 / 100	1012 ms	145576 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()

struct node {
	int sum=0;

	node(int _sum=0): sum(_sum){}
};

vector<node> nodes(1);
vi roots={0};
vi l(1,-1),r(1,-1);
int n;
vi a;

int getnode(int s=0) {
	nodes.pb(node(s));
	l.pb(-1);
	r.pb(-1);
	return nodes.size()-1;
}

void build(int v, int tl, int tr) {
	if (tl==tr) {
		return;
	}
	int tm=tl+(tr-tl)/2;
	l[v]=getnode();
	r[v]=getnode();
	build(l[v],tl,tm);
	build(r[v],tm+1,tr);
}

void update(int ov, int nv, int tl, int tr, int ind) {
	nodes[nv].sum=nodes[ov].sum+1;
	if (tl==tr) {
		return;
	}
	int tm=tl+(tr-tl)/2;
	if (ind<=tm) {
		l[nv]=getnode();
		r[nv]=r[ov];
		update(l[ov],l[nv],tl,tm,ind);
	}
	else {
		l[nv]=l[ov];
		r[nv]=getnode();
		update(r[ov],r[nv],tm+1,tr,ind);
	}
}

int get(int v, int tl, int tr, int lb, int rb) {
	if (lb<=tl && tr<=rb) {
		return nodes[v].sum;
	}
	if (tr<lb || rb<tl) {
		return 0;
	}
	int tm=tl+(tr-tl)/2;
	return get(l[v],tl,tm,lb,rb)+get(r[v],tm+1,tr,lb,rb);
}
int get(int la, int ra, int lb) {
	int l=lower_bound(all(a),la)-a.begin();
	int r=upper_bound(all(a),ra)-a.begin();
	return get(roots[r],0,n,lb,n)-get(roots[l],0,n,lb,n);
}

int findind(int v1, int v2, int lim, int tl, int tr) {
	if (tl==tr) {
		if (nodes[v1].sum-nodes[v2].sum>lim) {
			return tl+1;
		}
		return tl;
	}
	int tm=tl+(tr-tl)/2;
	if (nodes[r[v1]].sum-nodes[r[v2]].sum>lim) {
		return findind(r[v1],r[v2],lim,tm+1,tr);
	}
	return findind(l[v1],l[v2],lim-(nodes[r[v1]].sum-nodes[r[v2]].sum),tl,tm);
}
int findind(int la, int ra, int lim) {
	int l=lower_bound(all(a),la)-a.begin();
	int r=lower_bound(all(a),ra)-a.begin();
	return findind(roots[r],roots[l],lim,0,n);
}

void init(int _n, int _a[], int _b[]) {
	n=_n;
	build(0,0,n);
	vector<pi> p;
	for (int i=0; i<n; i++) {
		p.pb({_a[i],_b[i]});
		a.pb(_a[i]);
	}
	sort(all(p));
	sort(all(a));
	for (int i=0; i<n; i++) {
		roots.pb(getnode());
		update(roots[roots.size()-2],roots.back(),0,n,p[i].se);
	}
}

vi dp,k;
int m;

int clc(int a, int b) {
	//dp[b]-dp[a]<=get(k[a]+1,k[i],k[i])-get(k[b]+1,k[i],k[i])
    //dp[a]-dp[b]>=get(k[b]+1,k[i],k[i])-get(k[a]+1,k[i],k[i])
	return findind(k[b]+1,k[a]+1,dp[a]-dp[b]);
}

int can(int _m, int _k[]) {
	m=_m;
	k.clear();
	k.pb(0);
	for (int i=0; i<m; i++) {
		k.pb(_k[i]);
	}
	sort(all(k));
	m++;
	dp.resize(m,0);
	set<int> stk={0};
	set<pi> q;
	map<int,int> ertm;
	for (int i=1; i<m; i++) {
		while (q.size() && q.begin()->fi<=k[i]) {
			auto it=next(stk.lower_bound(q.begin()->se));
			stk.erase(prev(it));
			q.erase(q.begin());
			if (it!=stk.end()) {
				q.erase({ertm[*it],*it});
				ertm[*it]=clc(*it,*prev(it));
				q.insert({ertm[*it],*it});
			}
		}
		if (k[*prev(stk.end())]==k[i]) {
			dp[i]=dp[*prev(stk.end())]-k[i];
			q.erase({ertm[*prev(stk.end())],*prev(stk.end())});
			stk.erase(prev(stk.end()));
			ertm[i]=clc(i,*prev(stk.end()));
			stk.insert(i);
			q.insert({ertm[i],i});
		}
		else {
			dp[i]=dp[*prev(stk.end())]+get(k[*prev(stk.end())]+1,k[i],k[i])-k[i];
			ertm[i]=clc(i,*prev(stk.end()));
			stk.insert(i);
			q.insert({ertm[i],i});
		}
		if (dp[i]<0) {
			return 0;
		}
	}
	return 1;
}

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