Submission #563374

#	Time	Username	Problem	Language	Result	Execution time	Memory
563374		HunterXD	Teams (IOI15_teams)	C++17	0 / 100	1652 ms	236760 KiB

teams

#include <bits/stdc++.h>
using namespace std;

typedef int ll;

#define f first 
#define s second 
#define pb push_back 

vector<ll> power = {1};
ll val_power = 25;

struct ST{

	ll l, r;
	ST *left = NULL, *right = NULL;
	vector<ll> arr, sum;
	ll arr_size = 0;
	ll marked = -1, lazy_marked = -1;

	bool reset = false;

	ST(ll i_l, ll i_r, vector< vector<ll> > *ar){
		l = i_l; r = i_r;

		if(l == r){
			arr = (*ar)[l];			
			arr_size = arr.size();
			sum.assign(arr_size, 0);
			sort(arr.begin(), arr.end(), greater<ll>());
			return;
		}

		ll med = (l+r)/2;
		left = new ST(l, med, ar);
		right = new ST(med+1, r, ar);

		arr_size = left->arr_size + right->arr_size;
		sum.assign(arr_size, 0);
		
		ll next = 0;

		vector<ll>::iterator it_l = left->arr.begin(), it_r = right->arr.begin();

		while(it_l != left->arr.end() && it_r != right->arr.end()){
			if(*it_l > *it_r){
				arr.pb(*(it_l++));
				if(next) sum[next] = sum[next-1]+1;
				else sum[next] = 1;
			} 
			else{
				arr.pb(*(it_r++));
				if(next) sum[next] = sum[next-1];
				else sum[next] = 0;
			} 
			next++;
		}

		while(it_l != left->arr.end()){
			arr.pb(*(it_l++));
			if(next) sum[next] = sum[next-1]+1;
			else sum[next] = 1;
			next++;
		}

		while(it_r != right->arr.end()){
			arr.pb(*(it_r++));
			if(next) sum[next] = sum[next-1];
			else sum[next] = 0;
			next++;
		} 
	}

	void apply_lazy_stuff(){
		if(l == r){
			if(reset){
				marked = -1;
				lazy_marked = -1;
				reset = false;
			}
			if(lazy_marked != -1){
				marked = lazy_marked;
				lazy_marked = -1;
			}
			return;
		}
		if(reset){
			left->reset = true;
			right->reset = true;
			marked = -1;
			lazy_marked = -1;
			reset = false;
		}

		if(lazy_marked != -1){
			marked = lazy_marked;
			left->lazy_marked = -1+sum[marked];
			right->lazy_marked = -1+(marked+1-sum[marked]);
			lazy_marked = -1;
		}
	}

	ll mark(ll s_l, ll s_r, ll i, ll k){
		apply_lazy_stuff();
		//si está fuera del rango

		//eliminamos elementos fuera del rango
		for(ll j = val_power; j >= 0; j--){
			if(marked+power[j] >= arr_size) continue;
			if(arr[marked+power[j]] > i) marked = marked+power[j];
		}

		if(r < s_l || s_r < l) return 0;
		//si no tiene elementos
		if(marked+1 == arr_size) return 0;

		//si está adentro del rango
		if( s_l <= l && r <= s_r ){
			if(l != r){
				left->apply_lazy_stuff();
				right->apply_lazy_stuff();
			}
			lazy_marked = min(arr_size-1, marked+k);
			ll res = lazy_marked-marked;
			marked = lazy_marked;
			return res;
		}

		//si alguna parte está afuera, vemos los dos, con prioridad en right
		ll r1 = right->mark(s_l, s_r, i, k);
		ll r2 = left->mark(s_l, s_r, i, k-r1);
		marked = left->marked + right->marked +1;
		return r1+r2;
	}	

};

ST *me = NULL;
ll on;

void init(ll n, ll a[], ll b[]) {

	on = n;

	for(ll i = 1; i <= val_power; i++){
		power.pb(2*power[i-1]);
	}

	vector< vector<ll> > my(n+1, vector<ll>());
	for(ll i = 0; i < n; i++){
		my[b[i]].pb(a[i]);
	}
	me = new ST(1, n, &my);
	
	
}

ll can(ll m, ll k[]) {
	me->reset = true;
	sort(k, k+m, greater<ll>());
	ll v,t;
	for(ll i = 0; i < m; i++){
		v = k[i];
		t = me->mark(v, on, v, v);
		if(t != v){
			return false;
		}
	}
	return true;
}

Compilation message (stderr)

teams.cpp: In constructor 'ST::ST(ll, ll, std::vector<std::vector<int> >*)':
teams.cpp:28:23: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} may change value [-Wconversion]
   28 |    arr_size = arr.size();
      |               ~~~~~~~~^~

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