Submission #221809

#	Time	Username	Problem	Language	Result	Execution time	Memory
221809		patrikpavic2	Teams (IOI15_teams)	C++17	100 / 100	1194 ms	413736 KiB

teams

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  teams
* score: 100.0
* date:  2019-06-25 17:32:34.665190
*/
#include "teams.h"
#include <algorithm>
#include <vector>
#include <set>
#include <cstdio>
#include <cstring>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef pair < int, int > pii;
typedef vector < int > vi;
typedef vector < pii > vp;
typedef long long ll;
typedef short int sint;

const int N = 5e5 + 500;
const int OFF = (1 << 19);

struct node{
	node* L;
	node* R;
	int sm;
	//int a, b, i;
};

node* root[N];
set < pii > ss;

void build(int i, node* x){
	if(i >= 2 * OFF) return;
	x -> L = new node(); x -> R = new node(); x -> sm = 0;
	build(2 * i, x -> L);
	build(2 * i + 1, x -> R);
}

void update(int a,int b,int c,node *x){
	if(a == b) return;
	if(c <= (a + b) / 2){
		node* y = new node();
		y -> sm = x -> L -> sm + 1;
		y -> L = x -> L -> L;
		y -> R = x -> L -> R;
		x -> L = y;
		update(a, (a + b) / 2, c, x -> L);
		return;
	}
	else{
		node* y = new node();
		y -> sm = x -> R -> sm + 1;
		y -> L = x -> R -> L;
		y -> R = x -> R -> R;
		x -> R = y;
		update((a + b) / 2 + 1, b, c, x -> R);
		return;
	}
}

int sp = -1;
int n, D[N], k[N], q, m, lst = 0, tez[N], mrt[N], lg[N];
set < int > s;
vi izb[N];

int W(int i,node* x1,node* x2,int k){
	if(i >= OFF) return i - OFF;
	int x = x2 -> R -> sm - x1 -> R -> sm;
	if(x >= k) 
		return W(2 * i + 1, x1 -> R, x2 -> R, k);
	return W(2 * i, x1 -> L, x2 -> L, k - x);
}

int Z(int a,int b,int lo,int hi,node* x1){
	if(lo <= a && b <= hi) return (x1 -> sm);
	if(a > hi || b < lo) return 0;
	//printf("z %d %d res : %d - %d\n", a, b, (x2 -> sm), (x1 -> sm));
	return Z(a, (a + b) / 2, lo, hi, x1 -> L) + Z((a + b) / 2 + 1, b, lo, hi, x1 -> R);
}

void izbaci(int x){
	//if(q == sp)printf("izbacujem %d\n", x);
	s.erase(x);
	auto it1 = s.lower_bound(x);
	if(it1 == s.end() || it1 == s.begin()) return;
	int j = *it1, i = *(--it1); 
	if(D[j] < D[i]) return;
	int kad = W(1, root[k[i]], root[k[j]], D[j] - D[i]); 
	//if(q == sp) printf("eksluzivno!! izbaci me {i = %d j = %d} u %d trebam %d\n", i, j, kad, D[j] - D[i]);		
	kad++;
	if(kad <= k[m - 1] && kad > lst) ss.insert({kad, j});
}

void init(int nn, int a[], int b[]) {
	n = nn;
	vector < pii > v;
	for(int i = 0;i < n;i++){
		v.PB({a[i], b[i]});
	}
	sort(v.begin(), v.end());
	int j = 0;
	root[0] = new node();
	build(1, root[0]); 
	for(int i = 1;i <= n;i++){
		root[i] = new node();
		root[i] -> sm = root[i - 1] -> sm;
		root[i] -> L = root[i - 1] -> L;
		root[i] -> R = root[i - 1] -> R;
		
		while(j < v.size() && v[j].X == i){
			update(0, OFF - 1, v[j++].Y, root[i]);
			root[i] -> sm++;
		}
	}
}


int can(int mm, int kk[]) {
	q++; m = 1;
	sort(kk, kk + mm);
	k[0] = kk[0], tez[0] = 1;
	for(int i = 1;i < mm;i++) {
		if(kk[i] == k[m - 1]){
			tez[m - 1]++;
		}
		else{
			k[m] = kk[i], tez[m++] = 1;
		}
		
	}
	s.clear();
	int ans = 0;
    lst = 0;
	for(int i = 0;i < m;i++){
		for(; !ss.empty() && ss.begin()->X <= k[i]; ){
			izbaci(ss.begin() -> Y);
			ss.erase(ss.begin());
		}
		int ubac = 1;
		D[i] = Z(0, OFF - 1, k[i], OFF - 1, root[k[i]]) - tez[i] * k[i];
		//printf("prije %d\n", D[i]);
		for(int j = 0;j < i;j++){
		}
	    if(!s.empty()){
			int j = *s.rbegin();
			//if(q == sp)printf("tu sam %d\n", k[j]);
			D[i] = min(D[i], D[j] + Z(0, OFF - 1, k[i], OFF - 1, root[k[i]]) - Z(0, OFF - 1, k[i], OFF - 1, root[k[j]]) - tez[i] * k[i]);
			if(D[i] > D[j]){				
				int kad =  W(1, root[k[j]], root[k[i]], D[i] - D[j]);
				kad++;
				if(kad <= k[i]) ubac = 0;
				else if(kad <= k[m - 1]) ss.insert({kad, i});
			}
		}
		if(ubac) s.insert(i);
		ans = min(ans, D[i]);
	}
	ss.clear();
	return ans >= 0;
}

Compilation message (stderr)

teams.cpp: In function 'int W(int, node*, node*, int)':
teams.cpp:75:36: warning: declaration of 'k' shadows a global declaration [-Wshadow]
 int W(int i,node* x1,node* x2,int k){
                                    ^
teams.cpp:71:14: note: shadowed declaration is here
 int n, D[N], k[N], q, m, lst = 0, tez[N], mrt[N], lg[N];
              ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:119:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < v.size() && v[j].X == i){
         ~~^~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23