oj.uz

Submission #1063618

# Submission time Handle Problem Language Result Execution time Memory
1063618 2024-08-17T21:20:55 Z jamjanek Comparing Plants (IOI20_plants) C++14
30 / 100
 4000 ms 133204 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;
}

pair<int, long long> prawo[200010][18], lewo[200010][18];
int skacz_prawo(int start, int odl){
	for(int j = 17;j>=0;j--)
		if(odl>=prawo[start][j].second){
			odl-=prawo[start][j].second;
			start = prawo[start][j].first;
		}
	return start;
}
int skacz_lewo(int start, int odl){
	for(int j = 17;j>=0;j--)
		if(odl>=lewo[start][j].second){
			odl-=lewo[start][j].second;
			start = lewo[start][j].first;
		}
	return start;
}

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");

	//skok w prawo
	for(i=0;i<n;i++){
		int bestval = -1;
		prawo[i][0] = {i, 0};
		for(int j=1;j<k;j++)
			if(perm[(i+j)%n]>bestval && perm[(i+j)%n]<perm[i]){
				prawo[i][0] = {(i+j)%n, j};
//				if(i==2)printf("!!!%d %d\n", prawo[i][0].first, j);
				bestval = perm[(i+j)%n];
			}
//		if(i==2)printf("!!!%d\n", prawo[i][0].first);
	}
	//skok w lewo
	for(i=0;i<n;i++){
		int bestval = -1;
		lewo[i][0] = {i, 0};
		for(int j=1;j<k;j++)
			if(perm[(n+i-j)%n]>bestval && perm[(n+i-j)%n]<perm[i]){
				lewo[i][0] = {(n+i-j)%n, j};
				bestval = perm[(n+i-j)%n];
			}
	}
	for(int j = 1;j<18;j++)
		for(i=0;i<n;i++){
			prawo[i][j] = {prawo[prawo[i][j-1].first][j-1].first,  prawo[i][j-1].second+ prawo[prawo[i][j-1].first][j-1].second};
			lewo[i][j] = {lewo[lewo[i][j-1].first][j-1].first,  lewo[i][j-1].second+ lewo[lewo[i][j-1].first][j-1].second};
		}
/*
	for(i=0;i<n;i++)printf("%d ", perm[i]);printf("\n");
	printf("PRAWO: ");for(i=0;i<n;i++)
		printf("%d-%d " ,prawo[i][0].first,prawo[i][0].second);printf("\n");
	printf("LEWO: ");for(i=0;i<n;i++)
		printf("%d-%d " ,lewo[i][0].first,lewo[i][0].second);printf("\n");
*/
	return;
}

int compare_plants(int x, int y) {
//	printf("%d %d\n", x, y);
	int odl, z;
	//w prawo od x
	odl = (n+y-x)%n;
//	printf("odl: %d\n", odl);
	z = skacz_prawo(x, odl);
//	printf("%d %d %d\n", x, y, z);
	if((n+y-z)%n<k && perm[z]>=perm[y])return 1;

	//w lowe od x
	odl = (n+x-y)%n;
	z = skacz_lewo(x, odl);
//	printf("odl: %d\n", odl);
//	printf("%d %d %d\n", x, y, z);
	if((n+z-y)%n<k && perm[z]>=perm[y])return 1;

	swap(x, y);
	//w prawo od x
	odl = (n+y-x)%n;
//	printf("odl: %d\n", odl);
//	for(int i=0;i<n;i++)printf("%d ", skacz_prawo[i]);
	z = skacz_prawo(x, odl);
//	exit(0);
	if((n+y-z)%n<k && perm[z]>=perm[y])return -1;

	//w lowe od x
	odl = (n+x-y)%n;
//	printf("odl: %d\n", odl);
	z = skacz_lewo(x, odl);
	if((n+z-y)%n<k && perm[z]>=perm[y])return -1;

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5712 KB Output is correct
2 Correct 39 ms 5712 KB Output is correct
3 Correct 39 ms 5692 KB Output is correct
4 Correct 38 ms 5716 KB Output is correct
5 Correct 39 ms 5712 KB Output is correct
6 Correct 98 ms 8532 KB Output is correct
7 Correct 138 ms 21588 KB Output is correct
8 Correct 470 ms 125816 KB Output is correct
9 Correct 472 ms 125528 KB Output is correct
10 Correct 435 ms 125520 KB Output is correct
11 Correct 437 ms 126032 KB Output is correct
12 Correct 467 ms 128748 KB Output is correct
13 Correct 370 ms 133204 KB Output is correct
14 Correct 501 ms 123988 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5712 KB Output is correct
2 Correct 38 ms 5808 KB Output is correct
3 Correct 39 ms 5716 KB Output is correct
4 Correct 38 ms 5708 KB Output is correct
5 Correct 39 ms 5720 KB Output is correct
6 Correct 52 ms 8192 KB Output is correct
7 Correct 246 ms 12868 KB Output is correct
8 Correct 40 ms 5968 KB Output is correct
9 Correct 46 ms 8016 KB Output is correct
10 Correct 229 ms 12968 KB Output is correct
11 Correct 147 ms 12884 KB Output is correct
12 Correct 175 ms 13036 KB Output is correct
13 Correct 308 ms 12884 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5712 KB Output is correct
2 Correct 38 ms 5808 KB Output is correct
3 Correct 39 ms 5716 KB Output is correct
4 Correct 38 ms 5708 KB Output is correct
5 Correct 39 ms 5720 KB Output is correct
6 Correct 52 ms 8192 KB Output is correct
7 Correct 246 ms 12868 KB Output is correct
8 Correct 40 ms 5968 KB Output is correct
9 Correct 46 ms 8016 KB Output is correct
10 Correct 229 ms 12968 KB Output is correct
11 Correct 147 ms 12884 KB Output is correct
12 Correct 175 ms 13036 KB Output is correct
13 Correct 308 ms 12884 KB Output is correct
14 Correct 1916 ms 21336 KB Output is correct
15 Execution timed out 4067 ms 13332 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5712 KB Output is correct
2 Correct 38 ms 5712 KB Output is correct
3 Correct 108 ms 10832 KB Output is correct
4 Correct 466 ms 124756 KB Output is correct
5 Correct 603 ms 125520 KB Output is correct
6 Correct 1613 ms 125260 KB Output is correct
7 Execution timed out 4102 ms 43440 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5712 KB Output is correct
2 Correct 67 ms 5712 KB Output is correct
3 Correct 38 ms 5724 KB Output is correct
4 Correct 67 ms 5716 KB Output is correct
5 Correct 65 ms 5716 KB Output is correct
6 Correct 71 ms 5968 KB Output is correct
7 Correct 57 ms 6484 KB Output is correct
8 Correct 51 ms 6484 KB Output is correct
9 Correct 87 ms 6480 KB Output is correct
10 Correct 55 ms 6576 KB Output is correct
11 Correct 55 ms 6420 KB Output is correct
12 Correct 63 ms 6604 KB Output is correct
13 Correct 50 ms 6480 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5716 KB Output is correct
2 Correct 57 ms 5680 KB Output is correct
3 Correct 39 ms 5644 KB Output is correct
4 Correct 41 ms 5768 KB Output is correct
5 Correct 41 ms 7932 KB Output is correct
6 Correct 607 ms 122024 KB Output is correct
7 Correct 1600 ms 121936 KB Output is correct
8 Execution timed out 4042 ms 35888 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5712 KB Output is correct
2 Correct 39 ms 5712 KB Output is correct
3 Correct 39 ms 5692 KB Output is correct
4 Correct 38 ms 5716 KB Output is correct
5 Correct 39 ms 5712 KB Output is correct
6 Correct 98 ms 8532 KB Output is correct
7 Correct 138 ms 21588 KB Output is correct
8 Correct 470 ms 125816 KB Output is correct
9 Correct 472 ms 125528 KB Output is correct
10 Correct 435 ms 125520 KB Output is correct
11 Correct 437 ms 126032 KB Output is correct
12 Correct 467 ms 128748 KB Output is correct
13 Correct 370 ms 133204 KB Output is correct
14 Correct 501 ms 123988 KB Output is correct
15 Correct 47 ms 5712 KB Output is correct
16 Correct 38 ms 5808 KB Output is correct
17 Correct 39 ms 5716 KB Output is correct
18 Correct 38 ms 5708 KB Output is correct
19 Correct 39 ms 5720 KB Output is correct
20 Correct 52 ms 8192 KB Output is correct
21 Correct 246 ms 12868 KB Output is correct
22 Correct 40 ms 5968 KB Output is correct
23 Correct 46 ms 8016 KB Output is correct
24 Correct 229 ms 12968 KB Output is correct
25 Correct 147 ms 12884 KB Output is correct
26 Correct 175 ms 13036 KB Output is correct
27 Correct 308 ms 12884 KB Output is correct
28 Correct 1916 ms 21336 KB Output is correct
29 Execution timed out 4067 ms 13332 KB Time limit exceeded
30 Halted 0 ms 0 KB -