oj.uz

Submission #77361

# Submission time Handle Problem Language Result Execution time Memory
77361 2018-09-26T05:28:03 Z shoemakerjo Teams (IOI15_teams) C++14
77 / 100
 1620 ms 525312 KB 
#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>

#define maxn 500010
vector<pii> stuff;
int n;

struct node {

	int ct;
	node *left; node *right;

	node (node *ll, node *rr, int cc) : 
		left(ll), right(rr), ct(cc) {}

	node * update(int lo, int hi, int spot, int diff);

};


node *roots[maxn];
vector<vector<int>> badds(maxn);
vector<vector<int>> bsubs(maxn);


node *null = new node(NULL, NULL, 0);

node * node :: update(int lo, int hi, int spot, int diff) {
	if (lo == hi) return new node(null, null, this->ct + diff);
	int mid = (lo + hi)/2;
	if (spot <= mid) {
		return new node(this->left->update(lo, mid, spot, diff),
		this->right, this->ct+diff);
	}
	return new node(this->left, this->right->update(mid+1, hi, spot, diff),
		 this->ct+diff);
}

void init(int N, int A[], int B[]) {
	// cout << "here" << endl;
	null->left = null;
	null->right = null;
	n = N;
	for (int i = 0; i < n; i++) {
		stuff.push_back(pii(B[i], A[i]));
	}
	sort(stuff.begin(), stuff.end());
	for (int i = 0; i < n; i++) {
		badds[stuff[i].second].push_back(i+1);
		bsubs[stuff[i].first+1].push_back(i+1);
	}
	roots[0] = null;
	for (int i = 1; i <= n; i++) {
		roots[i] = roots[i-1];
		for (int vv : badds[i]) roots[i] = roots[i]->update(1, n, vv, 1);
		for (int vv : bsubs[i]) roots[i] = roots[i]->update(1, n, vv, -1);

	}

}

node * remo(node * cur, int ss, int se, int qs, int qe) {
	if (qs > qe || ss > se || qs > se || qe < ss) return cur;
	if (qs <= ss && se <= qe) return null;
	int mid = (ss+se)/2;
	node *ll = remo(cur->left, ss, mid, qs, qe);
	node *rr = remo(cur->right, mid+1, se, qs, qe);
	return new node (ll, rr, ll->ct + rr->ct);
}

node * godown(node *used, node *active, int k, int ss, int se) {
	// cout << "   " << used->ct << " " << active ->ct << " " << k  << endl;
	assert(active ->ct - used ->ct >= k);
	assert(ss <= se);

	int lsub = active->left->ct - used->left->ct;
	int mid = (ss+se)/2;

	if (ss == se) {
		if (k == 0) {
			return used;
		}
		return active;
	}

	if (lsub >= k) {
	
		node *ll = godown(used->left, active->left, k, ss, mid);
		node *rr = used->right;
		return new node (ll, rr, ll->ct + rr->ct);
	}

	node *ll = active->left;
	node *rr = godown(used->right, active->right, k - lsub, mid+1, se);
	return new node(ll, rr, ll->ct + rr->ct);

}

node* takeout(int vv, node* used) {
	//remove duplicates correclty please
	//remove all less than a 
	int lo = 0;
	int hi = n-1;
	if (stuff[lo].first >= vv) {
		//nothing to remove
		return used;
	}
	while (lo < hi) {
		int mid = (lo+hi+1)/2;
		if (stuff[mid].first < vv) {
			lo = mid;
		}
		else hi = mid-1;
	}

	used = remo(used, 1, n, 1, lo+1); 
}

int can(int M, int K[]) {
	int lspot = 1;
	vector<int> vals;
	for (int i = 0; i < M; i++) {
		vals.push_back(K[i]);
	}
	sort(vals.begin(), vals.end());
	node * used = null;
	for (int vv : vals) {
		// cout << "going for " << vv << endl;
		used = takeout(vv, used);
		// cout << "   done removing" << endl;
		if (roots[vv]->ct - used->ct < vv) {
			// cout << "QUERY FAILED" << endl;
			return 0;
			// cout << "QUERY FAILED" << endl;
		}
		used = godown(used, roots[vv], vv, 1, n);
		//remove all b's less than the val that I have taken
	}
	// cout << "QUERY SUCCEEDED" << endl;
	return 1;

}

Compilation message

teams.cpp: In constructor 'node::node(node*, node*, int)':
teams.cpp:15:20: warning: 'node::right' will be initialized after [-Wreorder]
  node *left; node *right;
                    ^~~~~
teams.cpp:14:6: warning:   'int node::ct' [-Wreorder]
  int ct;
      ^~
teams.cpp:17:2: warning:   when initialized here [-Wreorder]
  node (node *ll, node *rr, int cc) : 
  ^~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:124:6: warning: unused variable 'lspot' [-Wunused-variable]
  int lspot = 1;
      ^~~~~
teams.cpp: In function 'node* takeout(int, node*)':
teams.cpp:121:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 23 ms 24064 KB Output is correct
3 Correct 23 ms 24064 KB Output is correct
4 Correct 23 ms 24212 KB Output is correct
5 Correct 23 ms 24212 KB Output is correct
6 Correct 24 ms 24312 KB Output is correct
7 Correct 25 ms 24780 KB Output is correct
8 Correct 23 ms 24780 KB Output is correct
9 Correct 23 ms 24780 KB Output is correct
10 Correct 24 ms 24780 KB Output is correct
11 Correct 22 ms 24780 KB Output is correct
12 Correct 25 ms 25056 KB Output is correct
13 Correct 24 ms 25056 KB Output is correct
14 Correct 23 ms 25056 KB Output is correct
15 Correct 24 ms 25056 KB Output is correct
16 Correct 24 ms 25056 KB Output is correct
17 Correct 24 ms 25056 KB Output is correct
18 Correct 23 ms 25056 KB Output is correct
19 Correct 23 ms 25056 KB Output is correct
20 Correct 23 ms 25056 KB Output is correct
21 Correct 23 ms 25056 KB Output is correct
22 Correct 29 ms 25056 KB Output is correct
23 Correct 23 ms 25056 KB Output is correct
24 Correct 23 ms 25056 KB Output is correct
25 Correct 23 ms 25056 KB Output is correct
26 Correct 28 ms 25056 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 142460 KB Output is correct
2 Correct 339 ms 143664 KB Output is correct
3 Correct 333 ms 144756 KB Output is correct
4 Correct 326 ms 147312 KB Output is correct
5 Correct 241 ms 147312 KB Output is correct
6 Correct 249 ms 147312 KB Output is correct
7 Correct 246 ms 147312 KB Output is correct
8 Correct 245 ms 147312 KB Output is correct
9 Correct 210 ms 147312 KB Output is correct
10 Correct 268 ms 157484 KB Output is correct
11 Correct 248 ms 157484 KB Output is correct
12 Correct 258 ms 157484 KB Output is correct
13 Correct 264 ms 157484 KB Output is correct
14 Correct 195 ms 157484 KB Output is correct
15 Correct 327 ms 157484 KB Output is correct
16 Correct 308 ms 157484 KB Output is correct
17 Correct 256 ms 157484 KB Output is correct
18 Correct 249 ms 157484 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 160332 KB Output is correct
2 Correct 346 ms 162024 KB Output is correct
3 Correct 648 ms 241680 KB Output is correct
4 Correct 368 ms 241680 KB Output is correct
5 Correct 524 ms 264964 KB Output is correct
6 Correct 464 ms 264964 KB Output is correct
7 Correct 250 ms 264964 KB Output is correct
8 Correct 403 ms 264964 KB Output is correct
9 Correct 217 ms 264964 KB Output is correct
10 Correct 437 ms 264964 KB Output is correct
11 Correct 399 ms 264964 KB Output is correct
12 Correct 575 ms 269384 KB Output is correct
13 Correct 716 ms 271948 KB Output is correct
14 Correct 716 ms 271948 KB Output is correct
15 Correct 474 ms 271948 KB Output is correct
16 Correct 466 ms 271948 KB Output is correct
17 Correct 419 ms 271948 KB Output is correct
18 Correct 418 ms 271948 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1620 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -