oj.uz

Submission #563024

# Submission time Handle Problem Language Result Execution time Memory
563024 2022-05-16T05:03:02 Z HunterXD Teams (IOI15_teams) C++17
0 / 100
 851 ms 524288 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 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 = val_power; 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;

ll on = 0; 
vector< vector<ll> > my;

void init(ll n, ll a[], ll b[]) {
	for(ll i = 1; i <= val_power; i++){
		power.pb(2*power[i-1]);
	}

	on = n;
	my.assign(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 = new ST(1, on, &my);
	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

teams.cpp: In constructor 'ST::ST(ll, ll, std::vector<std::vector<int> >*)':
teams.cpp:23:14: warning: declaration of 'r' shadows a member of 'ST' [-Wshadow]
   23 |  ST(ll l, ll r, vector< vector<ll> > *ar){
      |           ~~~^
teams.cpp:15:8: note: shadowed declaration is here
   15 |  ll l, r;
      |        ^
teams.cpp:23:8: warning: declaration of 'l' shadows a member of 'ST' [-Wshadow]
   23 |  ST(ll l, ll r, vector< vector<ll> > *ar){
      |     ~~~^
teams.cpp:15:5: note: shadowed declaration is here
   15 |  ll l, r;
      |     ^
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();
      |               ~~~~~~~~^~
teams.cpp: In constructor 'ST::ST(ll, ll, std::vector<std::vector<int> >*)':
teams.cpp:23:14: warning: declaration of 'r' shadows a member of 'ST' [-Wshadow]
   23 |  ST(ll l, ll r, vector< vector<ll> > *ar){
      |           ~~~^
teams.cpp:15:8: note: shadowed declaration is here
   15 |  ll l, r;
      |        ^
teams.cpp:23:8: warning: declaration of 'l' shadows a member of 'ST' [-Wshadow]
   23 |  ST(ll l, ll r, vector< vector<ll> > *ar){
      |     ~~~^
teams.cpp:15:5: note: shadowed declaration is here
   15 |  ll l, r;
      |     ^
teams.cpp: In constructor 'ST::ST(ll, ll, std::vector<std::vector<int> >*)':
teams.cpp:23:14: warning: declaration of 'r' shadows a member of 'ST' [-Wshadow]
   23 |  ST(ll l, ll r, vector< vector<ll> > *ar){
      |           ~~~^
teams.cpp:15:8: note: shadowed declaration is here
   15 |  ll l, r;
      |        ^
teams.cpp:23:8: warning: declaration of 'l' shadows a member of 'ST' [-Wshadow]
   23 |  ST(ll l, ll r, vector< vector<ll> > *ar){
      |     ~~~^
teams.cpp:15:5: note: shadowed declaration is here
   15 |  ll l, r;
      |     ^

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 5 ms 3424 KB Output is correct
4 Correct 5 ms 3412 KB Output is correct
5 Correct 5 ms 3412 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 3 ms 2988 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 4 ms 2900 KB Output is correct
13 Incorrect 3 ms 2900 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 86644 KB Output is correct
2 Correct 140 ms 86616 KB Output is correct
3 Correct 128 ms 86636 KB Output is correct
4 Correct 127 ms 87024 KB Output is correct
5 Correct 64 ms 71224 KB Output is correct
6 Correct 68 ms 71200 KB Output is correct
7 Correct 64 ms 71208 KB Output is correct
8 Correct 64 ms 71140 KB Output is correct
9 Correct 77 ms 70228 KB Output is correct
10 Correct 68 ms 70148 KB Output is correct
11 Correct 67 ms 70216 KB Output is correct
12 Correct 66 ms 70468 KB Output is correct
13 Correct 77 ms 73488 KB Output is correct
14 Correct 100 ms 79440 KB Output is correct
15 Incorrect 115 ms 86304 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 778 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 851 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -