oj.uz

Submission #304839

# Submission time Handle Problem Language Result Execution time Memory
304839 2020-09-22T01:26:01 Z arthur_nascimento Comparing Plants (IOI20_plants) C++14
44 / 100
 1664 ms 34668 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];

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]);

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

		vector<int> v = zeroes();

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

		int id = acha();

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

		
			
	}
	

}

void init(int k, std::vector<int> r) {
	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;
	if(H[0][x] > H[0][y])
		ans++;
	else ans--;
	if(H[1][x] > H[1][y])
		ans++;
	else ans--;
	return ans/2;
}

Compilation message

plants.cpp: In function 'void add(int)':
plants.cpp:95:8: warning: left operand of comma operator has no effect [-Wunused-value]
   95 |  debug("add %d:\n",x);
      |        ^~~~~~~~~~~
plants.cpp:119:8: warning: left operand of comma operator has no effect [-Wunused-value]
  119 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |        ^~~~~~~~~~~~~
plants.cpp:119:25: warning: right operand of comma operator has no effect [-Wunused-value]
  119 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |                      ~~~^~~~~
plants.cpp:128:8: warning: left operand of comma operator has no effect [-Wunused-value]
  128 |  debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
      |        ^~~~~~~~~~~~~
plants.cpp:128:30: warning: right operand of comma operator has no effect [-Wunused-value]
  128 |  debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
      |                      ~~~~~~~~^~
plants.cpp:133:8: warning: left operand of comma operator has no effect [-Wunused-value]
  133 |  debug(" +(%d,%d)\n",x,x-lst.first);
      |        ^~~~~~~~~~~~~
plants.cpp:133:30: warning: right operand of comma operator has no effect [-Wunused-value]
  133 |  debug(" +(%d,%d)\n",x,x-lst.first);
      |                              ^~~~~
plants.cpp:138:8: warning: statement has no effect [-Wunused-value]
  138 |  debug("\n\n");
      |       ~^~~~~~~
plants.cpp: In function 'void rem(int)':
plants.cpp:143:8: warning: left operand of comma operator has no effect [-Wunused-value]
  143 |  debug("rem %d:\n",x);
      |        ^~~~~~~~~~~
plants.cpp:161:8: warning: left operand of comma operator has no effect [-Wunused-value]
  161 |  debug(" -(%d,%d)\n",it.first,it.second);
      |        ^~~~~~~~~~~~~
plants.cpp:161:25: warning: right operand of comma operator has no effect [-Wunused-value]
  161 |  debug(" -(%d,%d)\n",it.first,it.second);
      |                      ~~~^~~~~
plants.cpp:162:8: warning: left operand of comma operator has no effect [-Wunused-value]
  162 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |        ^~~~~~~~~~~~~
plants.cpp:162:25: warning: right operand of comma operator has no effect [-Wunused-value]
  162 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |                      ~~~^~~~~
plants.cpp:173:8: warning: left operand of comma operator has no effect [-Wunused-value]
  173 |  debug(" +(%d,%d)\n",nx.first,nx.second+it.second);
      |        ^~~~~~~~~~~~~
plants.cpp:173:25: warning: right operand of comma operator has no effect [-Wunused-value]
  173 |  debug(" +(%d,%d)\n",nx.first,nx.second+it.second);
      |                      ~~~^~~~~
plants.cpp: In function 'int acha()':
plants.cpp:186:8: warning: left operand of comma operator has no effect [-Wunused-value]
  186 |  debug("tem %d\n",(int)S.size());
      |        ^~~~~~~~~~
plants.cpp: In function 'void go(int, int, int, std::vector<int>, int)':
plants.cpp:247:9: warning: left operand of comma operator has no effect [-Wunused-value]
  247 |   debug("pega %d\n",id);
      |         ^~~~~~~~~~~

Subtask #1
0 / 5.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 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.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 0 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 Correct 5 ms 512 KB Output is correct
7 Correct 90 ms 3648 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 95 ms 3576 KB Output is correct
11 Correct 94 ms 3716 KB Output is correct
12 Correct 81 ms 3704 KB Output is correct
13 Correct 89 ms 3576 KB Output is correct

Subtask #3
13.0 / 13.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 0 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 Correct 5 ms 512 KB Output is correct
7 Correct 90 ms 3648 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 95 ms 3576 KB Output is correct
11 Correct 94 ms 3716 KB Output is correct
12 Correct 81 ms 3704 KB Output is correct
13 Correct 89 ms 3576 KB Output is correct
14 Correct 163 ms 4572 KB Output is correct
15 Correct 1229 ms 15148 KB Output is correct
16 Correct 161 ms 4700 KB Output is correct
17 Correct 1271 ms 14948 KB Output is correct
18 Correct 1664 ms 24752 KB Output is correct
19 Correct 745 ms 14820 KB Output is correct
20 Correct 1072 ms 14832 KB Output is correct

Subtask #4
17.0 / 17.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 102 ms 3320 KB Output is correct
4 Correct 1217 ms 21384 KB Output is correct
5 Correct 1392 ms 16388 KB Output is correct
6 Correct 1492 ms 15208 KB Output is correct
7 Correct 1464 ms 15080 KB Output is correct
8 Correct 1289 ms 14952 KB Output is correct
9 Correct 1343 ms 19836 KB Output is correct
10 Correct 1375 ms 17068 KB Output is correct
11 Correct 1504 ms 34668 KB Output is correct
12 Correct 645 ms 14824 KB Output is correct
13 Correct 1653 ms 28580 KB Output is correct

Subtask #5
0 / 11.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 1 ms 384 KB Output isn't correct
4 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 1 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 5 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -