oj.uz

Submission #304840

# Submission time Handle Problem Language Result Execution time Memory
304840 2020-09-22T01:36:20 Z arthur_nascimento Comparing Plants (IOI20_plants) C++14
0 / 100
 4000 ms 2808 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define maxn 200200
#define inf 1000000
#define pii pair<int,int>
#define debug 
#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];

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;
}

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

	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[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[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;

void init(int k, std::vector<int> r) {
	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) {

	int ans = 0;
	go(R.size(), K, x, R, 0);
	if(antes[y])
		ans--;
	else ans++;

	go(R.size(), K, y, R, 0);
	if(antes[x])
		ans++;
	else ans--;

	return (ans/2);
}

Compilation message

plants.cpp: In function 'void add(int)':
plants.cpp:97:8: warning: left operand of comma operator has no effect [-Wunused-value]
   97 |  debug("add %d:\n",x);
      |        ^~~~~~~~~~~
plants.cpp:121:8: warning: left operand of comma operator has no effect [-Wunused-value]
  121 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |        ^~~~~~~~~~~~~
plants.cpp:121:25: warning: right operand of comma operator has no effect [-Wunused-value]
  121 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |                      ~~~^~~~~
plants.cpp:130:8: warning: left operand of comma operator has no effect [-Wunused-value]
  130 |  debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
      |        ^~~~~~~~~~~~~
plants.cpp:130:30: warning: right operand of comma operator has no effect [-Wunused-value]
  130 |  debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
      |                      ~~~~~~~~^~
plants.cpp:135:8: warning: left operand of comma operator has no effect [-Wunused-value]
  135 |  debug(" +(%d,%d)\n",x,x-lst.first);
      |        ^~~~~~~~~~~~~
plants.cpp:135:30: warning: right operand of comma operator has no effect [-Wunused-value]
  135 |  debug(" +(%d,%d)\n",x,x-lst.first);
      |                              ^~~~~
plants.cpp:140:8: warning: statement has no effect [-Wunused-value]
  140 |  debug("\n\n");
      |       ~^~~~~~~
plants.cpp: In function 'void rem(int)':
plants.cpp:145:8: warning: left operand of comma operator has no effect [-Wunused-value]
  145 |  debug("rem %d:\n",x);
      |        ^~~~~~~~~~~
plants.cpp:163:8: warning: left operand of comma operator has no effect [-Wunused-value]
  163 |  debug(" -(%d,%d)\n",it.first,it.second);
      |        ^~~~~~~~~~~~~
plants.cpp:163:25: warning: right operand of comma operator has no effect [-Wunused-value]
  163 |  debug(" -(%d,%d)\n",it.first,it.second);
      |                      ~~~^~~~~
plants.cpp:164:8: warning: left operand of comma operator has no effect [-Wunused-value]
  164 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |        ^~~~~~~~~~~~~
plants.cpp:164:25: warning: right operand of comma operator has no effect [-Wunused-value]
  164 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |                      ~~~^~~~~
plants.cpp:175:8: warning: left operand of comma operator has no effect [-Wunused-value]
  175 |  debug(" +(%d,%d)\n",nx.first,nx.second+it.second);
      |        ^~~~~~~~~~~~~
plants.cpp:175:25: warning: right operand of comma operator has no effect [-Wunused-value]
  175 |  debug(" +(%d,%d)\n",nx.first,nx.second+it.second);
      |                      ~~~^~~~~
plants.cpp: In function 'int acha()':
plants.cpp:188:8: warning: left operand of comma operator has no effect [-Wunused-value]
  188 |  debug("tem %d\n",(int)S.size());
      |        ^~~~~~~~~~
plants.cpp: In function 'void go(int, int, int, std::vector<int>, int)':
plants.cpp:254:9: warning: left operand of comma operator has no effect [-Wunused-value]
  254 |   debug("pega %d\n",id);
      |         ^~~~~~~~~~~

Subtask #1
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 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Execution timed out 4094 ms 2688 KB Time limit exceeded
7 Halted 0 ms 0 KB -

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 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 81 ms 384 KB Output is correct
6 Execution timed out 4085 ms 512 KB Time limit exceeded
7 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 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 81 ms 384 KB Output is correct
6 Execution timed out 4085 ms 512 KB Time limit exceeded
7 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 Correct 1 ms 384 KB Output is correct
3 Execution timed out 4061 ms 2808 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 36 ms 384 KB Output is correct
6 Correct 1783 ms 504 KB Output is correct
7 Execution timed out 4080 ms 896 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Execution timed out 4094 ms 384 KB Time limit exceeded
6 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 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Execution timed out 4094 ms 2688 KB Time limit exceeded
7 Halted 0 ms 0 KB -