oj.uz

Submission #77354

# Submission time Handle Problem Language Result Execution time Memory
77354 2018-09-26T03:42:41 Z shoemakerjo Teams (IOI15_teams) C++14
0 / 100
 1813 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++) {
		badds[A[i]].push_back(B[i]);
		bsubs[B[i]+1].push_back(B[i]);
	}
	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+1, vv, 1);
		for (int vv : bsubs[i]) roots[i] = roots[i]->update(1, n+1, 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) {
	// cout << "   " << used->ct << " " << active ->ct << " " << k  << endl;
	assert(active ->ct - used ->ct >= k);
	int lsub = active->left->ct - used->left->ct;
	if (lsub >= k) {
		if (lsub == k) {
			//need to remove everyting
			return new node(active->left, used->right, 
				active->left->ct + used->right->ct);
		}
		node *ll = godown(used->left, active->left, k);
		node *rr = active->right;
		return new node (ll, rr, ll->ct + rr->ct);
	}
	int rsub = active->right->ct - used->right->ct;
	if (lsub + rsub == k) {
		//must take all in the right subtree
		return active; //must take all in both
	}
	else {
		node *ll = active->left;
		node *rr = godown(used->right, active->right, k - lsub);
		return new node(ll, rr, ll->ct + rr->ct);
	}

}

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 = remo(used, 1, n+1, 1, vv-1); 
		// 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);
		//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:99:6: warning: unused variable 'lspot' [-Wunused-variable]
  int lspot = 1;
      ^~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 24112 KB Output is correct
3 Correct 24 ms 24296 KB Output is correct
4 Correct 23 ms 24460 KB Output is correct
5 Runtime error 50 ms 48048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 165068 KB Output is correct
2 Correct 330 ms 166240 KB Output is correct
3 Correct 329 ms 167368 KB Output is correct
4 Correct 351 ms 169880 KB Output is correct
5 Correct 228 ms 169880 KB Output is correct
6 Correct 237 ms 169880 KB Output is correct
7 Runtime error 386 ms 282140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 286940 KB Output is correct
2 Correct 336 ms 288548 KB Output is correct
3 Runtime error 523 ms 291588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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