제출 #613983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
613983		Mounir	식물 비교 (IOI20_plants)	C++14	27 / 100	313 ms	14948 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define pb push_back
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define x first
#define y second
using namespace std;
 
const int N = (1 << 18);
struct Noeud {
	int maxi, lazy;
};
 
Noeud arbre[N * 2];
void push(int noeud){
	for (int enf : {noeud * 2, noeud * 2 + 1}){
		arbre[enf].maxi += arbre[noeud].lazy;
		arbre[enf].lazy += arbre[noeud].lazy;
	}
 
	arbre[noeud].lazy = 0;
}
 
vector<int> candidats;
int k;
 
void getCandidats(int noeud, int res){
	if (noeud >= N) {
		candidats.pb(noeud - N);
		return;
	}
 
	push(noeud);
	for (int enf : {noeud * 2, noeud * 2 + 1}){
		if (arbre[enf].maxi == res)
			getCandidats(enf, res);
	}
}
 
void add(int noeud, int reql, int reqr, int curl, int curr){
	if (curr < reql || reqr < curl)
		return;
	if (reql <= curl && curr <= reqr){
		//cout << "reussi ! " << noeud << " " << arbre[noeud].maxi + 1 << endl;
		arbre[noeud].lazy ++;
		arbre[noeud].maxi ++;
		return;
	}
 
	push(noeud);
	int mid = (curl + curr)/2;
	add(noeud * 2, reql, reqr, curl, mid);
	add(noeud * 2 + 1, reql, reqr, mid + 1, curr);
	arbre[noeud].maxi = max(arbre[noeud * 2].maxi, arbre[noeud * 2 + 1].maxi);
}
 
void supprimer(int noeud){
	int nod = N + noeud;
	arbre[nod] = {-1, 0};
	nod /= 2;
	for (; nod > 0; nod /= 2)
		arbre[nod].maxi = max(arbre[nod * 2].maxi, arbre[nod * 2 + 1].maxi);
}
 
vector<int> num;
 
void init(int K, vector<int> plusGros) {
	int nVals = sz(plusGros);
	vector<int> fait(nVals, 0);
	num.resize(nVals);
	k = K;
	for (int nod = 1; nod < 2 * N; ++nod)
		arbre[nod] = {-1, 0};
	for (int i = 0; i < nVals; ++i)
		arbre[N + i].maxi = plusGros[i];
	for (int nod = N - 1; nod > 0; --nod)
		arbre[nod].maxi = max(arbre[nod * 2].maxi, arbre[nod * 2 + 1].maxi);
 
	int prochain = -1;
	set<int> enLice;
	for (int tour = 0; tour < nVals; ){
	//	cout << "tour " << tour << endl;
		candidats = {};
		getCandidats(1, k - 1);
		for (int candidat : candidats)
			enLice.insert(candidat);
		for (int candidat : candidats){
			auto it = enLice.lower_bound(candidat);
			if (it != enLice.begin()){
				it--;
				if (*it + k <= candidat)
					prochain = candidat;
			}
			else {
				it = enLice.end();
				--it;
				if (*it + k - nVals <= candidat)
					prochain = candidat;
			}
		}

		for (int candidat : candidats)
			supprimer(candidat);

	//	supprimer(prochain);
		num[prochain] = tour++;
		//cout << "num " << prochain << endl;
		int reql = prochain - k + 1, reqr = prochain - 1;
		if (reql < 0){
			add(1, 0, reqr, 0, N - 1);
			add(1, reql + nVals, nVals - 1, 0, N - 1);
		}
		else 
			add(1, reql, reqr, 0, N - 1);
		
		enLice.erase(prochain);
		auto it = enLice.lower_bound(prochain);
		if (it != enLice.end())
			prochain = *it;
		else if (!enLice.empty())
			prochain = *enLice.begin();
		else
			prochain = -1;
	}
}
 
int compare_plants(int x, int y) {
	if (num[x] < num[y])
		return -1;
	else
		return 1;
}

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25