Submission #77362

#	Time	Username	Problem	Language	Result	Execution time	Memory
77362		shoemakerjo	Teams (IOI15_teams)	C++14	77 / 100	1695 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++) {
		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 (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: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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23