Submission #67257

#	Time	Username	Problem	Language	Result	Execution time	Memory
67257		kingpig9	Teams (IOI15_teams)	C++11	77 / 100	3988 ms	525312 KiB

teams

//i submitted the others on oj.uz
#include <bits/stdc++.h>
#include "teams.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1 << 19;

//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N;

//persistent segment tree
struct node {
	node *ch[2];
	int lt, rt;
	int val;	//value

	node() {
		ch[0] = ch[1] = NULL;
	}

	node (int _lt, int _rt) {
		lt = _lt;
		rt = _rt;
		val = 0;

		if (rt - lt == 1) {
			ch[0] = ch[1] = NULL;
		} else {
			int mid = (lt + rt) / 2;
			ch[0] = new node(lt, mid);
			ch[1] = new node(mid, rt);
		}
	}

	node *update (int pos) {
		//this is the update of x
		if (lt <= pos && pos < rt) {
			node *res = new node();
			res->lt = this->lt;
			res->rt = this->rt;
			res->val = this->val + 1;
			if (rt == lt + 1) {
				res->ch[0] = res->ch[1] = NULL;
			} else {
				for (int i = 0; i < 2; i++) {
					res->ch[i] = this->ch[i]->update(pos);
				}
			}
			return res;
		} else {
			return this;
		}
	}

	int query (int a, int b) {
		if (this->rt <= a || b <= this->lt) {
			return 0;
		}

		if (a <= this->lt && this->rt <= b) {
			return this->val;
		}

		return this->ch[0]->query(a, b) + this->ch[1]->query(a, b);
	}
};

node* state[MAXN];	//state at certain point of time

void build (int n, int a[], int b[]) {
	vector<pii> v;
	for (int i = 0; i < n; i++) {
		v.push_back({a[i], b[i]});
	}
	sort(all(v));
	state[0] = new node(0, MAXN);
	for (int i = 1, ptr = 0; i <= n; i++) {
		state[i] = state[i - 1];
		while (ptr < v.size() && v[ptr].fi == i) {
			//then update this
			state[i] = state[i]->update(v[ptr].se);
			ptr++;
		}
	}
}

//ok this is used every query

#define ctime sdjfkj
#warning UPDATE CTIME ALWAYS!!!

int taken[2 * MAXN];
int lazy[2 * MAXN];	//used for ALL TAKEN only.
vector<int> vupds;

//ok this is now done every query - every query.
void reset() {
	for (int i : vupds) {
		taken[i] = 0;
		lazy[i] = 0;
	}
	vupds.clear();
}

void put (int cur, int lt, int rt, int v) {
	vupds.push_back(cur);

	//tree[cur] += v;
	//lazy[cur] += v;
	taken[cur] = state[v]->query(lt, rt);	//is this really it???? change "ctime" to "v"??
	lazy[cur] = v;
}

void down (int cur, int lt, int rt) {
	if (lazy[cur] != 0) {
		int mid = (lt + rt) / 2;
		put(2 * cur, lt, mid, lazy[cur]);
		put(2 * cur + 1, mid, rt, lazy[cur]);
		lazy[cur] = 0;
	}
}

void update_all (int a, int b, int v, int cur = 1, int lt = 0, int rt = MAXN) {
	if (rt <= a || b <= lt) {
		return;
	}

	if (a <= lt && rt <= b) {
		put(cur, lt, rt, v);
		return;
	}

	down(cur, lt, rt);
	int mid = (lt + rt) / 2;
	update_all(a, b, v, 2 * cur, lt, mid);
	update_all(a, b, v, 2 * cur + 1, mid, rt);
	taken[cur] = taken[2 * cur] + taken[2 * cur + 1];
	vupds.push_back(cur);
}

void update_single (int x, int v) {
	//taken[x] += v;
	for (int sh = 19, lt = 0, rt = MAXN; sh >= 1; sh--) {
		int cur = (x + MAXN) >> sh;
		down(cur, lt, rt);
		int mid = (lt + rt) / 2;

		if (x < mid) {
			//(lt, rt) -> (lt, mid)
			rt = mid;
		} else {
			//(lt, rt) -> (mid, rt)
			lt = mid;
		}
	}

	for (int i = x + MAXN; i > 0; i >>= 1) {
		vupds.push_back(i);
		taken[i] += v;
	}
}

int taken_query (int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
	if (rt <= a || b <= lt) {
		return 0;
	}
	
	if (a <= lt && rt <= b) {
		return taken[cur];
	}
	down(cur, lt, rt);

	int mid = (lt + rt) / 2;
	return taken_query(a, b, 2 * cur, lt, mid) + taken_query(a, b, 2 * cur + 1, mid, rt);
}

void init (int nnn, int a[], int b[]) {
	N = nnn;
	build(N, a, b);
	for (int i = 0; i < 2 * MAXN; i++) {
		taken[i] = 0;
		lazy[i] = 0;
	}
}

int can (int M, int K[]) {
	debug("-------------------START OF QUERY, M = %d---------------\n", M);
	if (accumulate(K, K + M, 0ll) > N) {
		return false;
	}

	reset();
	sort(K, K + M);

	for (int i = 0; i < M; i++) {
		int ctime = K[i];
		//check ptree.state[i]
		//binary search for it

		int nrem = state[ctime]->query(ctime, MAXN) - taken_query(ctime, MAXN);
		//how many are there left to take?
		if (K[i] > nrem) {
			debug("NOT ENOUGH!\n");
			return false;
		}

		//when will it be >= K[i]? And when is it < K[i]?
		int lo = ctime, hi = MAXN;
		while (hi - lo > 1) {
			int mid = (lo + hi) / 2;
			nrem = state[ctime]->query(ctime, mid) - taken_query(ctime, mid);
			if (nrem >= K[i]) {
				hi = mid;
			} else {
				lo = mid;
			}
		}

		int nall = state[ctime]->query(ctime, lo) - taken_query(ctime, lo);
		//[ctime, lo): take ALL.
		update_all(ctime, lo, ctime);
		//lo: take the remaining
		nrem = K[i] - nall;
		update_single(lo, nrem);
	}
	assert(taken[1] == accumulate(K, K + M, 0));
	return true;
}

Compilation message (stderr)

teams.cpp:99:2: warning: #warning UPDATE CTIME ALWAYS!!! [-Wcpp]
 #warning UPDATE CTIME ALWAYS!!!
  ^~~~~~~
teams.cpp: In function 'void build(int, int*, int*)':
teams.cpp:88:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (ptr < v.size() && v[ptr].fi == i) {
          ~~~~^~~~~~~~~~

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