제출 #604349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604349		balbit	팀들 (IOI15_teams)	C++14	34 / 100	4091 ms	12952 KiB

teams

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


#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;
	


}
int N;
vector<pii> seg;

int get(int L, int R) {
	// 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;
}

void init(signed NN, signed A[], signed B[]) {
	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);

}

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;
		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) - 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 - 1;
				while (bl != br) {
					int mid = (bl +br) / 2;
					int yum = get(mid, R) - get(prv, R) - (get(mid, sR) - get(prv, sR));
					bug(bl, br, mid, yum);
					bug(prv, sR, R);
					if(yum > need) {
						bl = mid+1;
					}else{
						br = mid;
					}
				}
				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: 0 / 43
• Subtask 4: 0 / 23