oj.uz

Submission #563373

# Submission time Handle Problem Language Result Execution time Memory
563373 2022-05-17T03:17:58 Z HunterXD Teams (IOI15_teams) C++17
0 / 100
 1664 ms 239196 KB 
#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);
			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;
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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Incorrect 2 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 47004 KB Output is correct
2 Correct 79 ms 47096 KB Output is correct
3 Correct 80 ms 47132 KB Output is correct
4 Correct 73 ms 47304 KB Output is correct
5 Correct 40 ms 38388 KB Output is correct
6 Correct 42 ms 38448 KB Output is correct
7 Incorrect 41 ms 38440 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 47460 KB Output is correct
2 Correct 90 ms 47500 KB Output is correct
3 Correct 489 ms 47488 KB Output is correct
4 Correct 78 ms 47424 KB Output is correct
5 Correct 230 ms 38708 KB Output is correct
6 Correct 136 ms 38724 KB Output is correct
7 Incorrect 250 ms 38672 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 239196 KB Output is correct
2 Correct 458 ms 238984 KB Output is correct
3 Correct 1664 ms 239036 KB Output is correct
4 Correct 436 ms 239012 KB Output is correct
5 Correct 970 ms 196368 KB Output is correct
6 Correct 646 ms 196340 KB Output is correct
7 Incorrect 985 ms 196380 KB Output isn't correct
8 Halted 0 ms 0 KB -