oj.uz

Submission #304826

# Submission time Handle Problem Language Result Execution time Memory
304826 2020-09-22T00:41:25 Z arthur_nascimento Comparing Plants (IOI20_plants) C++14
44 / 100
 872 ms 32876 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;

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

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

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});
		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(nx.first < x)
		nx.first += N;

	debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
	S.insert({nx.first%N,nx.first-x});
	Si.insert({nx.first-x,nx.first%N});
	debug(" +(%d,%d)\n",x,x-lst.first);
	S.insert({x,x-lst.first});
	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();
		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)));
	S.erase(S.find(nx));
	Si.erase(Si.find(rev(nx)));

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

int acha(){
	debug("tem %d\n",(int)S.size());
	return (--Si.end()) -> second;
	int ans = 0, opt = 0;
	for(auto i : S){
		debug("(%d;%d)\n",i.first,i.second);
		if(i.second > opt){
			opt = i.second;
			ans = i.first;
		}
	}
	return ans;
}

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

	N = n;

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

		int id = acha();

		rem(id);

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

		H[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);
	return;
}

int compare_plants(int x, int y) {
	if(H[x] > H[y])
		return 1;
	else
		return -1;
	return 0;
}

Compilation message

plants.cpp: In function 'void add(int)':
plants.cpp:93:8: warning: left operand of comma operator has no effect [-Wunused-value]
   93 |  debug("add %d:\n",x);
      |        ^~~~~~~~~~~
plants.cpp:116:8: warning: left operand of comma operator has no effect [-Wunused-value]
  116 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |        ^~~~~~~~~~~~~
plants.cpp:116:25: warning: right operand of comma operator has no effect [-Wunused-value]
  116 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |                      ~~~^~~~~
plants.cpp:123:8: warning: left operand of comma operator has no effect [-Wunused-value]
  123 |  debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
      |        ^~~~~~~~~~~~~
plants.cpp:123:30: warning: right operand of comma operator has no effect [-Wunused-value]
  123 |  debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
      |                      ~~~~~~~~^~
plants.cpp:126:8: warning: left operand of comma operator has no effect [-Wunused-value]
  126 |  debug(" +(%d,%d)\n",x,x-lst.first);
      |        ^~~~~~~~~~~~~
plants.cpp:126:30: warning: right operand of comma operator has no effect [-Wunused-value]
  126 |  debug(" +(%d,%d)\n",x,x-lst.first);
      |                              ^~~~~
plants.cpp:129:8: warning: statement has no effect [-Wunused-value]
  129 |  debug("\n\n");
      |       ~^~~~~~~
plants.cpp: In function 'void rem(int)':
plants.cpp:134:8: warning: left operand of comma operator has no effect [-Wunused-value]
  134 |  debug("rem %d:\n",x);
      |        ^~~~~~~~~~~
plants.cpp:151:8: warning: left operand of comma operator has no effect [-Wunused-value]
  151 |  debug(" -(%d,%d)\n",it.first,it.second);
      |        ^~~~~~~~~~~~~
plants.cpp:151:25: warning: right operand of comma operator has no effect [-Wunused-value]
  151 |  debug(" -(%d,%d)\n",it.first,it.second);
      |                      ~~~^~~~~
plants.cpp:152:8: warning: left operand of comma operator has no effect [-Wunused-value]
  152 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |        ^~~~~~~~~~~~~
plants.cpp:152:25: warning: right operand of comma operator has no effect [-Wunused-value]
  152 |  debug(" -(%d,%d)\n",nx.first,nx.second);
      |                      ~~~^~~~~
plants.cpp:158:8: warning: left operand of comma operator has no effect [-Wunused-value]
  158 |  debug(" +(%d,%d)\n",nx.first,nx.second+it.second);
      |        ^~~~~~~~~~~~~
plants.cpp:158:25: warning: right operand of comma operator has no effect [-Wunused-value]
  158 |  debug(" +(%d,%d)\n",nx.first,nx.second+it.second);
      |                      ~~~^~~~~
plants.cpp: In function 'int acha()':
plants.cpp:165:8: warning: left operand of comma operator has no effect [-Wunused-value]
  165 |  debug("tem %d\n",(int)S.size());
      |        ^~~~~~~~~~
plants.cpp:169:9: warning: left operand of comma operator has no effect [-Wunused-value]
  169 |   debug("(%d;%d)\n",i.first,i.second);
      |         ^~~~~~~~~~~
plants.cpp:169:23: warning: right operand of comma operator has no effect [-Wunused-value]
  169 |   debug("(%d;%d)\n",i.first,i.second);
      |                     ~~^~~~~
plants.cpp: In function 'void go(int, int, int, std::vector<int>)':
plants.cpp:198:9: warning: left operand of comma operator has no effect [-Wunused-value]
  198 |   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 1 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 0 ms 384 KB Output is correct
3 Correct 0 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 3 ms 512 KB Output is correct
7 Correct 77 ms 3576 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 84 ms 3576 KB Output is correct
11 Correct 82 ms 3708 KB Output is correct
12 Correct 80 ms 3704 KB Output is correct
13 Correct 77 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 0 ms 384 KB Output is correct
3 Correct 0 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 3 ms 512 KB Output is correct
7 Correct 77 ms 3576 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 84 ms 3576 KB Output is correct
11 Correct 82 ms 3708 KB Output is correct
12 Correct 80 ms 3704 KB Output is correct
13 Correct 77 ms 3576 KB Output is correct
14 Correct 116 ms 4572 KB Output is correct
15 Correct 662 ms 14200 KB Output is correct
16 Correct 118 ms 4492 KB Output is correct
17 Correct 656 ms 14200 KB Output is correct
18 Correct 872 ms 23396 KB Output is correct
19 Correct 423 ms 14200 KB Output is correct
20 Correct 575 ms 14072 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 72 ms 3316 KB Output is correct
4 Correct 602 ms 20396 KB Output is correct
5 Correct 614 ms 15552 KB Output is correct
6 Correct 740 ms 14200 KB Output is correct
7 Correct 758 ms 14200 KB Output is correct
8 Correct 675 ms 14208 KB Output is correct
9 Correct 664 ms 18800 KB Output is correct
10 Correct 683 ms 15608 KB Output is correct
11 Correct 751 ms 32876 KB Output is correct
12 Correct 362 ms 14076 KB Output is correct
13 Correct 833 ms 27460 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 512 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 288 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 #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 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -