oj.uz

Submission #1063604

# Submission time Handle Problem Language Result Execution time Memory
1063604 2024-08-17T21:14:43 Z jamjanek Comparing Plants (IOI20_plants) C++14
25 / 100
 4000 ms 122704 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][17], lewo[200010][17];
int skacz_prawo(int start, int odl){
	if(prawo[start][0].second==0)return start;
	if(odl<prawo[start][0].second)return start;
	return skacz_prawo(prawo[start][0].first, odl-prawo[start][0].second);
}
int skacz_lewo(int start, int odl){
	if(lewo[start][0].second==0)return start;
	if(odl<lewo[start][0].second)return start;
	return skacz_lewo(lewo[start][0].first, odl-lewo[start][0].second);
}

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(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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5852 KB Output is correct
2 Correct 38 ms 5980 KB Output is correct
3 Correct 39 ms 5848 KB Output is correct
4 Correct 40 ms 5824 KB Output is correct
5 Correct 39 ms 5980 KB Output is correct
6 Correct 76 ms 9552 KB Output is correct
7 Correct 221 ms 23892 KB Output is correct
8 Correct 330 ms 122456 KB Output is correct
9 Correct 445 ms 122268 KB Output is correct
10 Correct 1304 ms 122192 KB Output is correct
11 Execution timed out 4027 ms 122704 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5908 KB Output is correct
2 Correct 38 ms 5712 KB Output is correct
3 Correct 38 ms 5976 KB Output is correct
4 Correct 39 ms 5976 KB Output is correct
5 Correct 44 ms 5864 KB Output is correct
6 Correct 45 ms 8272 KB Output is correct
7 Correct 236 ms 14932 KB Output is correct
8 Correct 39 ms 5972 KB Output is correct
9 Correct 45 ms 8272 KB Output is correct
10 Correct 232 ms 15044 KB Output is correct
11 Correct 1152 ms 15188 KB Output is correct
12 Correct 1776 ms 15184 KB Output is correct
13 Correct 283 ms 14920 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5908 KB Output is correct
2 Correct 38 ms 5712 KB Output is correct
3 Correct 38 ms 5976 KB Output is correct
4 Correct 39 ms 5976 KB Output is correct
5 Correct 44 ms 5864 KB Output is correct
6 Correct 45 ms 8272 KB Output is correct
7 Correct 236 ms 14932 KB Output is correct
8 Correct 39 ms 5972 KB Output is correct
9 Correct 45 ms 8272 KB Output is correct
10 Correct 232 ms 15044 KB Output is correct
11 Correct 1152 ms 15188 KB Output is correct
12 Correct 1776 ms 15184 KB Output is correct
13 Correct 283 ms 14920 KB Output is correct
14 Correct 1915 ms 23640 KB Output is correct
15 Execution timed out 4041 ms 16976 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 5716 KB Output is correct
2 Correct 38 ms 5924 KB Output is correct
3 Correct 435 ms 12884 KB Output is correct
4 Execution timed out 4033 ms 121424 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5716 KB Output is correct
2 Correct 40 ms 5720 KB Output is correct
3 Correct 38 ms 5972 KB Output is correct
4 Correct 38 ms 5968 KB Output is correct
5 Correct 38 ms 5972 KB Output is correct
6 Correct 43 ms 6076 KB Output is correct
7 Correct 50 ms 6996 KB Output is correct
8 Correct 48 ms 6912 KB Output is correct
9 Correct 59 ms 6872 KB Output is correct
10 Correct 49 ms 6992 KB Output is correct
11 Correct 52 ms 6992 KB Output is correct
12 Correct 51 ms 7000 KB Output is correct
13 Correct 47 ms 6996 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5716 KB Output is correct
2 Correct 38 ms 5716 KB Output is correct
3 Correct 42 ms 5972 KB Output is correct
4 Correct 38 ms 5968 KB Output is correct
5 Correct 41 ms 8024 KB Output is correct
6 Correct 1092 ms 117844 KB Output is correct
7 Correct 2635 ms 117840 KB Output is correct
8 Execution timed out 4035 ms 38496 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5852 KB Output is correct
2 Correct 38 ms 5980 KB Output is correct
3 Correct 39 ms 5848 KB Output is correct
4 Correct 40 ms 5824 KB Output is correct
5 Correct 39 ms 5980 KB Output is correct
6 Correct 76 ms 9552 KB Output is correct
7 Correct 221 ms 23892 KB Output is correct
8 Correct 330 ms 122456 KB Output is correct
9 Correct 445 ms 122268 KB Output is correct
10 Correct 1304 ms 122192 KB Output is correct
11 Execution timed out 4027 ms 122704 KB Time limit exceeded
12 Halted 0 ms 0 KB -