Submission #77354

#	Time	Username	Problem	Language	Result	Execution time	Memory
77354		shoemakerjo	Teams (IOI15_teams)	C++14	0 / 100	1813 ms	525312 KiB

teams

#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 (stderr)

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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23