oj.uz

답안 #613983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613983 2022-07-30T15:33:50 Z Mounir 식물 비교 (IOI20_plants) C++14
27 / 100
 313 ms 14948 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Incorrect 3 ms 4308 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 3 ms 4328 KB Output is correct
6 Correct 5 ms 4436 KB Output is correct
7 Correct 56 ms 7244 KB Output is correct
8 Correct 4 ms 4436 KB Output is correct
9 Correct 5 ms 4436 KB Output is correct
10 Correct 58 ms 7292 KB Output is correct
11 Correct 51 ms 7164 KB Output is correct
12 Correct 55 ms 7500 KB Output is correct
13 Correct 55 ms 7244 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 3 ms 4328 KB Output is correct
6 Correct 5 ms 4436 KB Output is correct
7 Correct 56 ms 7244 KB Output is correct
8 Correct 4 ms 4436 KB Output is correct
9 Correct 5 ms 4436 KB Output is correct
10 Correct 58 ms 7292 KB Output is correct
11 Correct 51 ms 7164 KB Output is correct
12 Correct 55 ms 7500 KB Output is correct
13 Correct 55 ms 7244 KB Output is correct
14 Correct 70 ms 7496 KB Output is correct
15 Correct 262 ms 9892 KB Output is correct
16 Correct 87 ms 7472 KB Output is correct
17 Correct 313 ms 9964 KB Output is correct
18 Correct 206 ms 9896 KB Output is correct
19 Correct 264 ms 14948 KB Output is correct
20 Correct 258 ms 13212 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4308 KB Output is correct
2 Correct 3 ms 4308 KB Output is correct
3 Correct 53 ms 7236 KB Output is correct
4 Correct 179 ms 13412 KB Output is correct
5 Incorrect 201 ms 13732 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Incorrect 2 ms 4308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4328 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Incorrect 2 ms 4352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Incorrect 3 ms 4308 KB Output isn't correct
5 Halted 0 ms 0 KB -