oj.uz

Submission #67253

# Submission time Handle Problem Language Result Execution time Memory
67253 2018-08-13T17:37:37 Z kingpig9 Teams (IOI15_teams) C++11
77 / 100
 3984 ms 525312 KB 
//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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 57848 KB Output is correct
2 Correct 102 ms 57968 KB Output is correct
3 Correct 107 ms 58024 KB Output is correct
4 Correct 84 ms 58024 KB Output is correct
5 Correct 81 ms 58064 KB Output is correct
6 Correct 80 ms 58236 KB Output is correct
7 Correct 87 ms 58236 KB Output is correct
8 Correct 103 ms 58236 KB Output is correct
9 Correct 86 ms 58340 KB Output is correct
10 Correct 111 ms 58340 KB Output is correct
11 Correct 86 ms 58340 KB Output is correct
12 Correct 125 ms 58504 KB Output is correct
13 Correct 92 ms 58504 KB Output is correct
14 Correct 87 ms 58504 KB Output is correct
15 Correct 82 ms 58504 KB Output is correct
16 Correct 86 ms 58504 KB Output is correct
17 Correct 92 ms 58504 KB Output is correct
18 Correct 82 ms 58556 KB Output is correct
19 Correct 100 ms 58556 KB Output is correct
20 Correct 94 ms 58556 KB Output is correct
21 Correct 100 ms 58596 KB Output is correct
22 Correct 75 ms 58596 KB Output is correct
23 Correct 77 ms 58596 KB Output is correct
24 Correct 73 ms 58596 KB Output is correct
25 Correct 83 ms 58596 KB Output is correct
26 Correct 71 ms 58596 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 155148 KB Output is correct
2 Correct 331 ms 156220 KB Output is correct
3 Correct 321 ms 157368 KB Output is correct
4 Correct 331 ms 158728 KB Output is correct
5 Correct 243 ms 158728 KB Output is correct
6 Correct 244 ms 159112 KB Output is correct
7 Correct 238 ms 159780 KB Output is correct
8 Correct 223 ms 160556 KB Output is correct
9 Correct 1119 ms 194560 KB Output is correct
10 Correct 419 ms 194560 KB Output is correct
11 Correct 267 ms 194560 KB Output is correct
12 Correct 221 ms 194560 KB Output is correct
13 Correct 272 ms 194560 KB Output is correct
14 Correct 254 ms 194560 KB Output is correct
15 Correct 300 ms 194560 KB Output is correct
16 Correct 302 ms 194560 KB Output is correct
17 Correct 302 ms 194560 KB Output is correct
18 Correct 311 ms 194560 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 194560 KB Output is correct
2 Correct 346 ms 194560 KB Output is correct
3 Correct 2792 ms 194560 KB Output is correct
4 Correct 442 ms 194560 KB Output is correct
5 Correct 1763 ms 194560 KB Output is correct
6 Correct 1345 ms 194560 KB Output is correct
7 Correct 235 ms 194560 KB Output is correct
8 Correct 1299 ms 194560 KB Output is correct
9 Correct 1118 ms 210248 KB Output is correct
10 Correct 1399 ms 210248 KB Output is correct
11 Correct 1741 ms 210248 KB Output is correct
12 Correct 2930 ms 210248 KB Output is correct
13 Correct 3984 ms 210248 KB Output is correct
14 Correct 3805 ms 210248 KB Output is correct
15 Correct 1771 ms 210248 KB Output is correct
16 Correct 1848 ms 210248 KB Output is correct
17 Correct 1577 ms 210248 KB Output is correct
18 Correct 1549 ms 210248 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1749 ms 525312 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -