oj.uz

Submission #608431

# Submission time Handle Problem Language Result Execution time Memory
608431 2022-07-27T07:36:29 Z balbit Teams (IOI15_teams) C++14
100 / 100
 1822 ms 329932 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 313352 KB Output is correct
2 Correct 121 ms 313392 KB Output is correct
3 Correct 139 ms 313364 KB Output is correct
4 Correct 130 ms 313400 KB Output is correct
5 Correct 132 ms 313296 KB Output is correct
6 Correct 147 ms 313372 KB Output is correct
7 Correct 129 ms 313300 KB Output is correct
8 Correct 128 ms 313420 KB Output is correct
9 Correct 130 ms 313336 KB Output is correct
10 Correct 153 ms 313376 KB Output is correct
11 Correct 133 ms 313404 KB Output is correct
12 Correct 116 ms 313420 KB Output is correct
13 Correct 117 ms 313388 KB Output is correct
14 Correct 135 ms 313316 KB Output is correct
15 Correct 134 ms 313308 KB Output is correct
16 Correct 139 ms 313364 KB Output is correct
17 Correct 164 ms 313328 KB Output is correct
18 Correct 135 ms 313416 KB Output is correct
19 Correct 125 ms 313324 KB Output is correct
20 Correct 116 ms 313384 KB Output is correct
21 Correct 168 ms 313396 KB Output is correct
22 Correct 172 ms 313352 KB Output is correct
23 Correct 125 ms 313292 KB Output is correct
24 Correct 139 ms 313320 KB Output is correct
25 Correct 135 ms 313320 KB Output is correct
26 Correct 147 ms 313296 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 315456 KB Output is correct
2 Correct 202 ms 315480 KB Output is correct
3 Correct 184 ms 315496 KB Output is correct
4 Correct 181 ms 315700 KB Output is correct
5 Correct 169 ms 315432 KB Output is correct
6 Correct 152 ms 315496 KB Output is correct
7 Correct 147 ms 315456 KB Output is correct
8 Correct 154 ms 315504 KB Output is correct
9 Correct 168 ms 315504 KB Output is correct
10 Correct 142 ms 315500 KB Output is correct
11 Correct 147 ms 315440 KB Output is correct
12 Correct 154 ms 315456 KB Output is correct
13 Correct 171 ms 315404 KB Output is correct
14 Correct 173 ms 315488 KB Output is correct
15 Correct 173 ms 315380 KB Output is correct
16 Correct 198 ms 315500 KB Output is correct
17 Correct 181 ms 315488 KB Output is correct
18 Correct 167 ms 315476 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 315712 KB Output is correct
2 Correct 228 ms 315724 KB Output is correct
3 Correct 517 ms 318640 KB Output is correct
4 Correct 189 ms 315704 KB Output is correct
5 Correct 208 ms 315792 KB Output is correct
6 Correct 210 ms 315716 KB Output is correct
7 Correct 212 ms 315704 KB Output is correct
8 Correct 238 ms 315684 KB Output is correct
9 Correct 153 ms 315456 KB Output is correct
10 Correct 151 ms 315748 KB Output is correct
11 Correct 173 ms 315660 KB Output is correct
12 Correct 351 ms 315712 KB Output is correct
13 Correct 622 ms 315844 KB Output is correct
14 Correct 729 ms 317320 KB Output is correct
15 Correct 304 ms 315856 KB Output is correct
16 Correct 312 ms 315776 KB Output is correct
17 Correct 243 ms 315764 KB Output is correct
18 Correct 201 ms 315692 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 323944 KB Output is correct
2 Correct 528 ms 323948 KB Output is correct
3 Correct 1734 ms 329932 KB Output is correct
4 Correct 464 ms 323904 KB Output is correct
5 Correct 365 ms 324036 KB Output is correct
6 Correct 319 ms 324008 KB Output is correct
7 Correct 366 ms 323952 KB Output is correct
8 Correct 355 ms 323960 KB Output is correct
9 Correct 217 ms 323848 KB Output is correct
10 Correct 236 ms 324064 KB Output is correct
11 Correct 319 ms 323948 KB Output is correct
12 Correct 623 ms 324220 KB Output is correct
13 Correct 1358 ms 324148 KB Output is correct
14 Correct 1822 ms 327052 KB Output is correct
15 Correct 534 ms 324052 KB Output is correct
16 Correct 575 ms 324288 KB Output is correct
17 Correct 375 ms 324096 KB Output is correct
18 Correct 410 ms 324044 KB Output is correct