oj.uz

Submission #1063512

# Submission time Handle Problem Language Result Execution time Memory
1063512 2024-08-17T19:43:59 Z jamjanek Comparing Plants (IOI20_plants) C++14
44 / 100
 296 ms 20636 KB 
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
int perm[200010];
queue<int>kolejka;
set<int>zera;
int n,  k;
bool dodane[200010];
int nast(int val){
	if(zera.size()==0)return -1;
	if(zera.upper_bound(val)==zera.end()){
		return *zera.begin();
	}
	return *zera.upper_bound(val);
}
void rozpatrz(int val){
	if(val==-1)return;
	if(dodane[val])return;
	if(zera.lower_bound(val)==zera.begin()){
		int pom = *zera.rbegin();
		if(val - pom+n > k-1){
			kolejka.push(val);
			dodane[val] = 1;
		}
		return;
	}
	else{
		auto it = zera.lower_bound(val);
		it--;
		int pom =*it;
		if(val-pom > k-1){
			kolejka.push(val);
			dodane[val] = 1;
		}
	}
}
const int base = 1<<18;
int mini[2*base];
int lazy[2*base];

void push(int w){
	if(!lazy[w])return;
	mini[w*2]+=lazy[w];
	lazy[w*2]+=lazy[w];
	mini[w*2+1]+=lazy[w];
	lazy[w*2+1]+=lazy[w];
	mini[w] = min(mini[w*2], mini[w*2+1]);
	lazy[w] = 0;
}

void dodaj(int w, int l, int p, int a, int b, int val){
	if(b<l || p<a)return;
	if(a<=l && p<=b){
		mini[w]+=val;
		lazy[w]+=val;
		return;
	}
	push(w);
	dodaj(w*2, l, (l+p)/2, a, b, val);
	dodaj(w*2+1, (l+p)/2+1, p, a, b, val);
	mini[w] = min(mini[w*2], mini[w*2+1]);
}

void odejmij(int l, int p){
	l = (l+n)%n, p = (p+n)%n;
	if(l<=p)
		dodaj(1, 0, base-1, l, p, -1);
	else{
		dodaj(1, 0, base-1, l, n-1, -1);
		dodaj(1, 0, base-1, 0, p, -1);		
	}
}
int znajdz(int w){
	if(w>=base){
		if(mini[w]==0)return w-base;
		else return -1;
	}
	if(mini[w]>0)return -1;
	push(w);
	int pom = znajdz(w*2);
	if(pom==-1)pom = znajdz(w*2+1);
	else znajdz(w*2+1);
	mini[w] = min(mini[w*2], mini[w*2+1]);
	return pom;
}
void init(int K, std::vector<int> r) {
	n = r.size();
	int i;
	k = K;
	//odzyskaj permutacje

	for(i=0;i<n;i++)
		if(r[i]==0)
			zera.insert(i);
	for(auto j: zera){
		rozpatrz(j);
	}
	for(i=0;i<base;i++){
		if(i>=n || r[i]==0)
			dodaj(1, 0, base-1, i, i, 1000000000);
		else
			dodaj(1, 0, base-1, i, i, r[i]);
	}
	int numer = n-1;
	while(kolejka.size()){
		auto x = kolejka.front();
//		printf("%d:\n", x);
		kolejka.pop();
		perm[x] = numer--;
		zera.erase(x);
		odejmij(x-k+1, x-1);
		vector<int>nowe_zera;
		while(mini[1]==0){
			int j = znajdz(1);
//			printf("%d\n", j);
			dodaj(1, 0, base-1, j, j, 1000000000);
//			for(i=1;i<2*base;i++)printf("%d-%d ", mini[i], lazy[i]);printf("\n");
//			printf("drzewo\n");
//			exit(0);
			zera.insert(j);
			nowe_zera.push_back(j);
		}
		for(auto j: nowe_zera)
			rozpatrz(j);
		rozpatrz(nast(x));
//		for(auto j: nowe_zera)printf("%d ", j);
//		printf("\nKONIEC %d\n", x);
	}
//	for(i=0;i<n;i++)printf("%d ", perm[i]);printf("\n");
	return;
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3408 KB Output is correct
2 Correct 38 ms 3412 KB Output is correct
3 Correct 38 ms 3408 KB Output is correct
4 Incorrect 44 ms 3412 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 39 ms 3508 KB Output is correct
2 Correct 38 ms 3420 KB Output is correct
3 Correct 38 ms 3412 KB Output is correct
4 Correct 38 ms 3412 KB Output is correct
5 Correct 39 ms 3408 KB Output is correct
6 Correct 40 ms 3412 KB Output is correct
7 Correct 78 ms 8260 KB Output is correct
8 Correct 41 ms 3408 KB Output is correct
9 Correct 40 ms 3412 KB Output is correct
10 Correct 74 ms 8148 KB Output is correct
11 Correct 81 ms 8272 KB Output is correct
12 Correct 72 ms 8272 KB Output is correct
13 Correct 74 ms 8288 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3508 KB Output is correct
2 Correct 38 ms 3420 KB Output is correct
3 Correct 38 ms 3412 KB Output is correct
4 Correct 38 ms 3412 KB Output is correct
5 Correct 39 ms 3408 KB Output is correct
6 Correct 40 ms 3412 KB Output is correct
7 Correct 78 ms 8260 KB Output is correct
8 Correct 41 ms 3408 KB Output is correct
9 Correct 40 ms 3412 KB Output is correct
10 Correct 74 ms 8148 KB Output is correct
11 Correct 81 ms 8272 KB Output is correct
12 Correct 72 ms 8272 KB Output is correct
13 Correct 74 ms 8288 KB Output is correct
14 Correct 93 ms 8784 KB Output is correct
15 Correct 296 ms 12880 KB Output is correct
16 Correct 91 ms 8788 KB Output is correct
17 Correct 289 ms 12768 KB Output is correct
18 Correct 257 ms 16976 KB Output is correct
19 Correct 204 ms 12880 KB Output is correct
20 Correct 274 ms 13140 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3408 KB Output is correct
2 Correct 38 ms 3452 KB Output is correct
3 Correct 72 ms 8048 KB Output is correct
4 Correct 202 ms 15068 KB Output is correct
5 Correct 253 ms 12784 KB Output is correct
6 Correct 274 ms 12372 KB Output is correct
7 Correct 279 ms 12628 KB Output is correct
8 Correct 282 ms 12628 KB Output is correct
9 Correct 250 ms 14420 KB Output is correct
10 Correct 232 ms 13016 KB Output is correct
11 Correct 198 ms 20636 KB Output is correct
12 Correct 191 ms 12112 KB Output is correct
13 Correct 279 ms 18772 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3412 KB Output is correct
2 Correct 39 ms 3260 KB Output is correct
3 Incorrect 40 ms 3408 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3412 KB Output is correct
2 Correct 39 ms 3408 KB Output is correct
3 Incorrect 38 ms 3412 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3408 KB Output is correct
2 Correct 38 ms 3412 KB Output is correct
3 Correct 38 ms 3408 KB Output is correct
4 Incorrect 44 ms 3412 KB Output isn't correct
5 Halted 0 ms 0 KB -