oj.uz

Submission #77362

# Submission time Handle Problem Language Result Execution time Memory
77362 2018-09-26T05:31:27 Z shoemakerjo Teams (IOI15_teams) C++14
77 / 100
 1695 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 sum = 0;
	for (int i = 0; i < M; i++) {
		sum += K[i];
	}
	if (sum > n) return 0;

	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:131: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 23800 KB Output is correct
2 Correct 23 ms 23960 KB Output is correct
3 Correct 24 ms 23960 KB Output is correct
4 Correct 23 ms 23980 KB Output is correct
5 Correct 25 ms 24164 KB Output is correct
6 Correct 23 ms 24216 KB Output is correct
7 Correct 25 ms 24580 KB Output is correct
8 Correct 24 ms 24584 KB Output is correct
9 Correct 25 ms 24584 KB Output is correct
10 Correct 24 ms 24584 KB Output is correct
11 Correct 23 ms 24584 KB Output is correct
12 Correct 26 ms 25000 KB Output is correct
13 Correct 27 ms 25000 KB Output is correct
14 Correct 29 ms 25000 KB Output is correct
15 Correct 23 ms 25000 KB Output is correct
16 Correct 23 ms 25000 KB Output is correct
17 Correct 24 ms 25000 KB Output is correct
18 Correct 24 ms 25000 KB Output is correct
19 Correct 23 ms 25000 KB Output is correct
20 Correct 24 ms 25000 KB Output is correct
21 Correct 24 ms 25000 KB Output is correct
22 Correct 26 ms 25000 KB Output is correct
23 Correct 24 ms 25000 KB Output is correct
24 Correct 22 ms 25000 KB Output is correct
25 Correct 23 ms 25000 KB Output is correct
26 Correct 23 ms 25000 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 142140 KB Output is correct
2 Correct 352 ms 143404 KB Output is correct
3 Correct 346 ms 144588 KB Output is correct
4 Correct 365 ms 147176 KB Output is correct
5 Correct 245 ms 147176 KB Output is correct
6 Correct 239 ms 147176 KB Output is correct
7 Correct 241 ms 147176 KB Output is correct
8 Correct 245 ms 147176 KB Output is correct
9 Correct 218 ms 147176 KB Output is correct
10 Correct 277 ms 157312 KB Output is correct
11 Correct 261 ms 157312 KB Output is correct
12 Correct 250 ms 157312 KB Output is correct
13 Correct 295 ms 157312 KB Output is correct
14 Correct 202 ms 157312 KB Output is correct
15 Correct 320 ms 157312 KB Output is correct
16 Correct 322 ms 157312 KB Output is correct
17 Correct 255 ms 157312 KB Output is correct
18 Correct 260 ms 157312 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 160264 KB Output is correct
2 Correct 376 ms 161940 KB Output is correct
3 Correct 628 ms 241440 KB Output is correct
4 Correct 360 ms 241440 KB Output is correct
5 Correct 518 ms 264744 KB Output is correct
6 Correct 472 ms 264744 KB Output is correct
7 Correct 273 ms 264744 KB Output is correct
8 Correct 425 ms 264744 KB Output is correct
9 Correct 214 ms 264744 KB Output is correct
10 Correct 414 ms 264744 KB Output is correct
11 Correct 404 ms 264744 KB Output is correct
12 Correct 556 ms 269304 KB Output is correct
13 Correct 630 ms 271644 KB Output is correct
14 Correct 713 ms 271644 KB Output is correct
15 Correct 486 ms 271644 KB Output is correct
16 Correct 485 ms 271644 KB Output is correct
17 Correct 418 ms 271644 KB Output is correct
18 Correct 424 ms 271644 KB Output is correct

Subtask #4
0 / 23.0

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