oj.uz

Submission #304841

# Submission time Handle Problem Language Result Execution time Memory
304841 2020-09-22T01:40:17 Z arthur_nascimento Comparing Plants (IOI20_plants) C++14
11 / 100
 2087 ms 9168 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];

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;

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[x][y])
		ans--;
	else ans++;

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

	return (ans/2);
}

Compilation message

plants.cpp: In function 'void add(int)':
plants.cpp:99:8: warning: left operand of comma operator has no effect [-Wunused-value]
   99 |  debug("add %d:\n",x);
      |        ^~~~~~~~~~~
plants.cpp:123:8: warning: left operand of comma operator has no effect [-Wunused-value]
  123 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |        ^~~~~~~~~~~~~
plants.cpp:123:25: warning: right operand of comma operator has no effect [-Wunused-value]
  123 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |                      ~~~^~~~~
plants.cpp:132:8: warning: left operand of comma operator has no effect [-Wunused-value]
  132 |  debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
      |        ^~~~~~~~~~~~~
plants.cpp:132:30: warning: right operand of comma operator has no effect [-Wunused-value]
  132 |  debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
      |                      ~~~~~~~~^~
plants.cpp:137:8: warning: left operand of comma operator has no effect [-Wunused-value]
  137 |  debug(" +(%d,%d)\n",x,x-lst.first);
      |        ^~~~~~~~~~~~~
plants.cpp:137:30: warning: right operand of comma operator has no effect [-Wunused-value]
  137 |  debug(" +(%d,%d)\n",x,x-lst.first);
      |                              ^~~~~
plants.cpp:142:8: warning: statement has no effect [-Wunused-value]
  142 |  debug("\n\n");
      |       ~^~~~~~~
plants.cpp: In function 'void rem(int)':
plants.cpp:147:8: warning: left operand of comma operator has no effect [-Wunused-value]
  147 |  debug("rem %d:\n",x);
      |        ^~~~~~~~~~~
plants.cpp:165:8: warning: left operand of comma operator has no effect [-Wunused-value]
  165 |  debug(" -(%d,%d)\n",it.first,it.second);
      |        ^~~~~~~~~~~~~
plants.cpp:165:25: warning: right operand of comma operator has no effect [-Wunused-value]
  165 |  debug(" -(%d,%d)\n",it.first,it.second);
      |                      ~~~^~~~~
plants.cpp:166:8: warning: left operand of comma operator has no effect [-Wunused-value]
  166 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |        ^~~~~~~~~~~~~
plants.cpp:166:25: warning: right operand of comma operator has no effect [-Wunused-value]
  166 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |                      ~~~^~~~~
plants.cpp:177:8: warning: left operand of comma operator has no effect [-Wunused-value]
  177 |  debug(" +(%d,%d)\n",nx.first,nx.second+it.second);
      |        ^~~~~~~~~~~~~
plants.cpp:177:25: warning: right operand of comma operator has no effect [-Wunused-value]
  177 |  debug(" +(%d,%d)\n",nx.first,nx.second+it.second);
      |                      ~~~^~~~~
plants.cpp: In function 'int acha()':
plants.cpp:190:8: warning: left operand of comma operator has no effect [-Wunused-value]
  190 |  debug("tem %d\n",(int)S.size());
      |        ^~~~~~~~~~
plants.cpp: In function 'void go(int, int, int, std::vector<int>, int)':
plants.cpp:261:9: warning: left operand of comma operator has no effect [-Wunused-value]
  261 |   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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 88 ms 3192 KB Output is correct
7 Runtime error 112 ms 8576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.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 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 9 ms 512 KB Output is correct
6 Incorrect 1212 ms 2040 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 9 ms 512 KB Output is correct
6 Incorrect 1212 ms 2040 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 Runtime error 796 ms 9168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
11.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 2 ms 384 KB Output is correct
6 Correct 23 ms 512 KB Output is correct
7 Correct 221 ms 1400 KB Output is correct
8 Correct 164 ms 1528 KB Output is correct
9 Correct 171 ms 1528 KB Output is correct
10 Correct 155 ms 1400 KB Output is correct
11 Correct 209 ms 1400 KB Output is correct
12 Correct 196 ms 1404 KB Output is correct
13 Correct 104 ms 1400 KB Output is correct

Subtask #6
0 / 15.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 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 2087 ms 1760 KB Output isn't correct
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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 88 ms 3192 KB Output is correct
7 Runtime error 112 ms 8576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -