Submission #563018

#	Time	Username	Problem	Language	Result	Execution time	Memory
563018		HunterXD	Teams (IOI15_teams)	C++17	0 / 100	1413 ms	243656 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};

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 l, ll r, vector< vector<ll> > *ar){
		this->l = l; this->r = 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++;
		} 
	}

	ll next_marked(ll k){
		ll next = marked+1;
		for(ll i = 19; i >= 0; i--){
			if(next+power[i] >= arr_size) continue;
			if(arr[next+power[i]] >= k) next = next+power[i];
		}
		return 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

		if(r < s_l || s_r < l) return 0;
		//si no tiene elementos
		if(marked+1 == arr_size) return 0;
		//si no hay elementos libres mayores o igual a i
		if(arr[marked+1] < i) 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(next_marked(i), marked+k);
			return lazy_marked-marked;
		}

		//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);
		return r1+r2;
	}	

};

ST *me = NULL;

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

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

	vector< vector<ll> > my(n+1, vector<ll>());
	for(ll i = 0; i < n; i++){
		my[a[i]].pb(b[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(1, v, 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:22:14: warning: declaration of 'r' shadows a member of 'ST' [-Wshadow]
   22 |  ST(ll l, ll r, vector< vector<ll> > *ar){
      |           ~~~^
teams.cpp:14:8: note: shadowed declaration is here
   14 |  ll l, r;
      |        ^
teams.cpp:22:8: warning: declaration of 'l' shadows a member of 'ST' [-Wshadow]
   22 |  ST(ll l, ll r, vector< vector<ll> > *ar){
      |     ~~~^
teams.cpp:14:5: note: shadowed declaration is here
   14 |  ll l, r;
      |     ^
teams.cpp:27:23: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} may change value [-Wconversion]
   27 |    arr_size = arr.size();
      |               ~~~~~~~~^~
teams.cpp: In constructor 'ST::ST(ll, ll, std::vector<std::vector<int> >*)':
teams.cpp:22:14: warning: declaration of 'r' shadows a member of 'ST' [-Wshadow]
   22 |  ST(ll l, ll r, vector< vector<ll> > *ar){
      |           ~~~^
teams.cpp:14:8: note: shadowed declaration is here
   14 |  ll l, r;
      |        ^
teams.cpp:22:8: warning: declaration of 'l' shadows a member of 'ST' [-Wshadow]
   22 |  ST(ll l, ll r, vector< vector<ll> > *ar){
      |     ~~~^
teams.cpp:14:5: note: shadowed declaration is here
   14 |  ll l, r;
      |     ^
teams.cpp: In constructor 'ST::ST(ll, ll, std::vector<std::vector<int> >*)':
teams.cpp:22:14: warning: declaration of 'r' shadows a member of 'ST' [-Wshadow]
   22 |  ST(ll l, ll r, vector< vector<ll> > *ar){
      |           ~~~^
teams.cpp:14:8: note: shadowed declaration is here
   14 |  ll l, r;
      |        ^
teams.cpp:22:8: warning: declaration of 'l' shadows a member of 'ST' [-Wshadow]
   22 |  ST(ll l, ll r, vector< vector<ll> > *ar){
      |     ~~~^
teams.cpp:14:5: note: shadowed declaration is here
   14 |  ll l, r;
      |     ^

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