oj.uz

Submission #304814

# Submission time Handle Problem Language Result Execution time Memory
304814 2020-09-22T00:09:45 Z arthur_nascimento Comparing Plants (IOI20_plants) C++14
14 / 100
 4000 ms 18416 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;

void add(int x){
	S.insert({x,0});
}

void rem(int x){
	auto it = S.lower_bound({x,-1});
	S.erase(it);
}

int acha(){
	debug("tem %d\n",(int)S.size());
	int last = (*--S.end()).first-N;
	int ans = 0, opt = 0;
	for(auto i : S){
		if(i.first - last > opt){
			opt = i.first - last;
			ans = i.first;
		}
		last = 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);

		//pii u = *--Si.end();
		//int id = u.second;

		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 'int acha()':
plants.cpp:97:8: warning: left operand of comma operator has no effect [-Wunused-value]
   97 |  debug("tem %d\n",(int)S.size());
      |        ^~~~~~~~~~
plants.cpp: In function 'void go(int, int, int, std::vector<int>)':
plants.cpp:133:9: warning: left operand of comma operator has no effect [-Wunused-value]
  133 |   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 Incorrect 0 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 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 Correct 3 ms 512 KB Output is correct
7 Correct 83 ms 3576 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 81 ms 3576 KB Output is correct
11 Correct 149 ms 3704 KB Output is correct
12 Correct 80 ms 3704 KB Output is correct
13 Correct 86 ms 3576 KB Output is correct

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 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 Correct 3 ms 512 KB Output is correct
7 Correct 83 ms 3576 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 81 ms 3576 KB Output is correct
11 Correct 149 ms 3704 KB Output is correct
12 Correct 80 ms 3704 KB Output is correct
13 Correct 86 ms 3576 KB Output is correct
14 Correct 114 ms 4564 KB Output is correct
15 Correct 616 ms 14072 KB Output is correct
16 Correct 117 ms 4700 KB Output is correct
17 Correct 627 ms 14072 KB Output is correct
18 Execution timed out 4054 ms 18416 KB Time limit exceeded
19 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 Correct 87 ms 3324 KB Output is correct
4 Execution timed out 4027 ms 16844 KB Time limit exceeded
5 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 0 ms 384 KB Output is correct
3 Incorrect 1 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

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