제출 #304814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
304814		arthur_nascimento	식물 비교 (IOI20_plants)	C++14	14 / 100	4054 ms	18416 KiB

plants

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

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25