Submission #608431

#	Time	Username	Problem	Language	Result	Execution time	Memory
608431		balbit	Teams (IOI15_teams)	C++14	100 / 100	1822 ms	329932 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

// #undef BALBIT
// #define int ll

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define FOR(i,a,b) for (int i = a; i<b; ++i) 
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<":"<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif

namespace {
	const int maxn = 5e5+10;
	const ll inf = 0x3f3f3f3f3f3f3f3f;
	const int BA= 40;
}
int N;
vector<pii> seg;

namespace MAO{
	int lc[maxn*BA], rc[maxn*BA], val[maxn*BA];
	int history[maxn];
	int IT = 1;
	int MO(int p, int o, int l, int r) {
		if (l > p || r < p) return o;
		int NO = ++IT;
		val[NO] = val[o] + 1;
		if (l == r) {
			return NO;
		}
		int mid = (l+r)/2;
		lc[NO] = MO(p,lc[o],l,mid);
		rc[NO] = MO(p,rc[o],mid+1,r);
		return NO;
	}
	int build(int l, int r) {
		int NO = ++IT;
		if (l == r) {
			return NO;
		}
		int mid = (l+r)/2;
		lc[NO] = build(l,mid); rc[NO] = build(mid+1,r);
		return NO;
	}

	int yeah[maxn*BA];

	vector<int> yoo;

	int QU(int L, int R, int o, int l, int r) {
		// bug(p,l,r,o,val[o]);
		if (~yeah[o]) return yeah[o];
		if (l > R || r < L) return 0;
		if (l >= L && r <= R) {
			return val[o];
		}
		int mid = (l+r) >> 1;
		yoo.pb(o);
		return yeah[o] = QU(L,R,lc[o],l,mid) + QU(L,R,rc[o],mid+1,r);
	}

	int QUsimple(int L, int R, int o, int l, int r) {
		// bug(p,l,r,o,val[o]);
		if (l > R || r < L) return 0;
		if (l >= L && r <= R) {
			return val[o];
		}
		int mid = (l+r) >> 1;
		return QUsimple(L,R,lc[o],l,mid) + QUsimple(L,R,rc[o],mid+1,r);
	}

}



inline int get(int L, int Ra, int Rb, bool rep=0) {
	// temporary function
	// returns the number of segments with index >= L && right value >= R
	// to be replaced by segtree later
	// int re = 0;
	// for(int i = L; i<N; ++i) {
	// 	if(seg[i].s >= R) re++;
	// }
	// return re;
	if (L >= N || Ra > N || Ra-1 > Rb) return 0;
	// bug(L,R);
	MX(L, 0);
	int ret = rep?MAO::QU(Ra-1, Rb-1,MAO::history[L],0,N-1) : MAO::QUsimple(Ra-1, Rb-1,MAO::history[L],0,N-1);
	return ret;
}

void init(signed NN, signed A[], signed B[]) {
	memset(MAO::lc, -1, sizeof MAO::lc);
	memset(MAO::rc, -1, sizeof MAO::rc);
	memset(MAO::yeah, -1, sizeof MAO::yeah);
	memset(MAO::val, 0, sizeof MAO::val);
	N = NN;
	seg.clear();
	REP(i,N) {
		seg.pb({A[i], B[i]});
	}
	sort(ALL(seg));
	REP(i, N)bug(i,seg[i].f,seg[i].s);
	MAO::history[N] = MAO::build(0, N-1);
	bug(MAO::history[N]);
	for(int i = N-1; i>=0; --i) {
		MAO::history[i] = MAO::MO(seg[i].s-1,MAO::history[i+1],0,N-1);
	}
	// bug(MAO::QU(0,MAO::history[0],0,N-1));
	// bug(MAO::QU(1,MAO::history[0],0,N-1));
	// bug(MAO::QU(2,MAO::history[0],0,N-1));
	// bug(MAO::QU(3,MAO::history[0],0,N-1));
}

struct item{
	int L, R;
};

signed can(signed M, signed K[]) {
	bug(M);
	map<int, int> take;
	REP(i,M) {
		take[K[i]]+=K[i];
		if (take[K[i]] > N) return 0;
	}
	vector<pii> tmp;
	for(pii p :take) {
		tmp.pb(p);
	}
	sort(ALL(tmp), greater<pii>());

	vector<item > stk; // {L, R}
	stk.pb({-1, N+1});
	int goback = N;
	for (auto PPP :tmp) {
		int R = PPP.f;
		int need = PPP.s;
		{
			int bl = 0, br = goback;
			while (bl != br) {
				int mid = (bl + br) / 2;
				if(seg[mid].f > R) {
					br = mid;
				}else{
					bl = mid+1;
				}
			}
			goback = bl;
		}
		// while(goback-1 >= 0 && seg[goback-1].f > R) --goback;
		int lastl = goback;
		while (!stk.empty()) {
			int sL = stk.back().L, sR = stk.back().R; 
			if (sL >= lastl) {
				stk.pop_back(); continue;
			}
			// indicates that, of all segments of index in [sL, lastl), 
			// anything with right value >= sR was taken
			int prv = lastl; lastl = sL;
			int haverem = +get(sL, R, sR-1) 
						-get(prv, R, sR-1);

			// (get(sL,R) - get(prv,R)) - (get(sL,sR) - get(prv, sR));

			bug(haverem);
			if (haverem < need) {
				need -= haverem;
				stk.pop_back();
				continue;
			}else if (haverem == need) {
				bug(haverem, need);
				need -= haverem;
				stk.back().R = R; 
				break;
			}else{
				bug(need);
				int bl = sL + 1, br = prv - need;

				for (int e : MAO::yoo) {
					MAO::yeah[e] = -1;
				}
				MAO::yoo.clear();

				int fix = -get(prv, R,sR-1);
				
				// {
				// 	int yar = fix +get(br, R, sR-1);
				// 	if(yar == need) {
				// 		bl = br;
				// 	}
				// }

				while (bl != br) {
					int mid = (bl +br) / 2;
					int yum = fix + get(mid, R, sR-1,1) ;
					bug(bl, br, mid, yum);
					bug(prv, sR, R);
					if (yum == need){
						bl = br = mid; break;
					}
					if(yum > need) {
						bl = mid+(yum-need);
					}else{
						br = mid-(need-yum);
					}
				}
				bug("add", bl, R);
				stk.push_back({bl, R});
				break;
			}
		}
		if(stk.empty()) return 0;
	}
	bug("yay");
	
	return 1;
}
/*
8
1 4
2 3
2 3
2 3
2 3
2 4
2 4
2 4
1
3 2 3 4

*/

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