oj.uz

Submission #304842

# Submission time Handle Problem Language Result Execution time Memory
304842 2020-09-22T01:47:01 Z arthur_nascimento Comparing Plants (IOI20_plants) C++14
5 / 100
 107 ms 5880 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define maxn 200200
#define inf 1000000
#define pii pair<int,int>
#define debug printf
#define pb push_back

int N,K;

int T[4*maxn];
int id[4*maxn];
int lazy[8*maxn];

int H[2][maxn];

//int antes[maxn];

int antes[330][330];

void refresh(int ini,int fim,int p){
	lazy[2*p] += lazy[p];
	lazy[2*p+1] += lazy[p];
	T[p] -= lazy[p];
	lazy[p] = 0;
}

void upd(int ini,int fim,int p,int pos,int val){
	refresh(ini,fim,p);
	if(pos < ini || pos > fim) return;
	if(ini == fim){
		T[p] = val;
		id[p] = pos;
		return;
	}
	int mid = (ini+fim)/2;
	upd(ini,mid,2*p,pos,val);
	upd(mid+1,fim,2*p+1,pos,val);

	if(T[2*p] < T[2*p+1]){
		T[p] = T[2*p];
		id[p] = id[2*p];
	}
	else {
		T[p] = T[2*p+1];
		id[p] = id[2*p+1];
	}
}

void dec(int ini,int fim,int p,int l,int r){
	refresh(ini,fim,p);
	if(l > fim || r < ini)
		return;
	if(ini >= l && fim <= r){
		lazy[p]++;
		refresh(ini,fim,p);
		return;
	}

	int mid = (ini+fim)/2;

	dec(ini,mid,2*p,l,r);
	dec(mid+1,fim,2*p+1,l,r);

	if(T[2*p] < T[2*p+1]){
		T[p] = T[2*p];
		id[p] = id[2*p];
	}
	else {
		T[p] = T[2*p+1];
		id[p] = id[2*p+1];
	}
	
}

vector<int> zeroes(){
	vector<int> ret;
	while(T[1] == 0){
		int pos = id[1];
		ret.pb(pos);
		upd(0,N-1,1,pos,inf);
	}
	return ret;
}

set<pii> S;
set<pii> Si;

set<int> Sgg;

pii rev(pii a){
	return {a.second,a.first};
}

void add(int x){

	debug("add %d:\n",x);

	if(S.size() == 0){
		S.insert({x,N});
		Si.insert({N,x});
		if(N >= K) Sgg.insert(x);
		return;
	}
	
	pii nx;
	if(S.lower_bound({x,inf}) != S.end())
		nx = *S.lower_bound({x,inf});
	else {
		nx = *S.begin();
	}
	
	pii lst;
	if(S.lower_bound({x,inf}) != S.begin())
		lst = *--S.lower_bound({x,inf});
	else {
		lst = *--S.end();
		lst.first -= N;
	}

	debug(" -(%d,%d)\n",nx.first,nx.second);
	S.erase(S.find(nx));
	Si.erase(Si.find(rev(nx)));
	if(Sgg.find(nx.first) != Sgg.end())
		Sgg.erase(Sgg.find(nx.first));

	if(nx.first < x)
		nx.first += N;

	debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
	S.insert({nx.first%N,nx.first-x});
	if(nx.first-x >= K)
		Sgg.insert(nx.first%N);
	Si.insert({nx.first-x,nx.first%N});
	debug(" +(%d,%d)\n",x,x-lst.first);
	S.insert({x,x-lst.first});
	if(x-lst.first >= K)
		Sgg.insert(x);
	Si.insert({x-lst.first,x});
	debug("\n\n");
}

void rem(int x){

	debug("rem %d:\n",x);

	if(S.size() == 1){
		S.clear();
		Si.clear();
		Sgg.clear();
		return;
	}

	pii it = *S.lower_bound({x,-1});
	

	pii nx;
	if(S.lower_bound({x,inf}) != S.end())
		nx = *S.lower_bound({x,inf});
	else
		nx = *S.begin();

	debug(" -(%d,%d)\n",it.first,it.second);
	debug(" -(%d,%d)\n",nx.first,nx.second);
	S.erase(S.find(it));
	Si.erase(Si.find(rev(it)));
	if(Sgg.find(it.first) != Sgg.end())
		Sgg.erase(Sgg.find(it.first));
		
	S.erase(S.find(nx));
	Si.erase(Si.find(rev(nx)));
	if(Sgg.find((nx.first)) != Sgg.end())
		Sgg.erase(Sgg.find(nx.first));

	debug(" +(%d,%d)\n",nx.first,nx.second+it.second);
	S.insert({nx.first,nx.second+it.second});
	Si.insert({nx.second+it.second,nx.first});

	if(nx.second+it.second >= K)
		Sgg.insert(nx.first);
	
}

int X,FX;
int consX;

int acha(){
	debug("tem %d\n",(int)S.size());

	//return *Sgg.begin();

	if(FX){

		if(*Sgg.begin() == 0)
			return 0;

		if(consX)
			return *Sgg.begin();

		else
			return *--Sgg.end();
		
	}
	
	if(Si.size() == 1 || FX)
		return (--Si.end()) -> second;
	
	int ret = (--Si.end()) -> second;

	if(FX == 0 && ret == X && S.size() > 1){
		pii retret = *----Si.end();
		if(retret.first >= K)
			return retret.second;
	}

	return ret;
}

int any_call[maxn];

void go(int n, int k, int x, vector<int> r,int fastx){

	if(any_call[x]) return;
	any_call[x] = 1;

	S.clear();
	Si.clear();
	
	N = n;
	X = x;
	FX = fastx;
	K = k;

	consX = 1;

	for(int i=0;i<n;i++)
		upd(0,N-1,1,i,r[i]), antes[x][i] = 0;

	int foi = 0;

	int foiX = 0;
	
	while(foi < n){

		vector<int> v = zeroes();

		for(int i : v){
			add(i);
			if(i == x) consX = 0;
		}

		int id = acha();

		if(id == X) foiX = 1;
		if(foiX == 0) antes[x][id] = 1;

		rem(id);

		debug("pega %d\n",id);

		H[fastx][id] = n-foi;
		foi++;

		dec(0,N-1,1,max(0,id-k+1),id-1);

		if(id-k+1 < 0)

			dec(0,N-1,1,id-k+1+N,N-1);

		
			
	}
	

}

vector<int> R;

int sum[maxn];

int ps(int a,int b){
	int ret = sum[b];
	if(a) ret -= sum[a-1];
	return ret;
}

void init(int k, std::vector<int> r) {
	sum[0] = r[0];
	N = r.size();
	for(int i=1;i<N;i++)
		sum[i] = sum[i-1] + r[i];
	R=r;K=k;
	return;
	go(r.size(), k, 0, r, 0);
	go(r.size(), k, 0, r, 1);
	return;
}

int compare_plants(int x, int y) {

	if(x > y)
		return -compare_plants(y,x);

	if(ps(x,y-1) == 0) return 1;
	if(ps(x,y-1) == y-x) return -1;
	if(ps(y,N-1) + ps(0, x-1) == 0) return -1;
	if(ps(y,N-1) + ps(0, x-1) == N-y + x) return 1;
	return 0;
	
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 66 ms 3192 KB Output is correct
7 Correct 82 ms 3448 KB Output is correct
8 Correct 102 ms 5752 KB Output is correct
9 Correct 107 ms 5752 KB Output is correct
10 Correct 105 ms 5880 KB Output is correct
11 Correct 105 ms 5880 KB Output is correct
12 Correct 103 ms 5796 KB Output is correct
13 Correct 105 ms 5752 KB Output is correct
14 Correct 105 ms 5752 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 66 ms 3192 KB Output is correct
7 Correct 82 ms 3448 KB Output is correct
8 Correct 102 ms 5752 KB Output is correct
9 Correct 107 ms 5752 KB Output is correct
10 Correct 105 ms 5880 KB Output is correct
11 Correct 105 ms 5880 KB Output is correct
12 Correct 103 ms 5796 KB Output is correct
13 Correct 105 ms 5752 KB Output is correct
14 Correct 105 ms 5752 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Incorrect 0 ms 384 KB Output isn't correct
18 Halted 0 ms 0 KB -