oj.uz

Submission #1063629

# Submission time Handle Problem Language Result Execution time Memory
1063629 2024-08-17T21:35:44 Z jamjanek Comparing Plants (IOI20_plants) C++14
27 / 100
 820 ms 134996 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
	set<pair<int,int>>sasiedzi;
	for(i=0;i<k-1;i++)
		sasiedzi.insert({perm[i], i});
	for(i=n-1;i>=0;i--){
		if(sasiedzi.lower_bound({perm[i], i})==sasiedzi.begin())
			prawo[i][0] = {i,0};
		else{
			auto it = sasiedzi.lower_bound({perm[i], i});
			it--;
			prawo[i][0] = {(*it).second, (n+(*it).second-i)%n};
		}
		sasiedzi.erase({perm[(i+k-1)%n], (i+k-1)%n});
		sasiedzi.insert({perm[i], i});
	}
	//lewo
	sasiedzi.clear();
	for(i=0;i<k-1;i++)
		sasiedzi.insert({perm[n-i-1], n-i-1});
	for(i=0;i<n;i++){
		if(sasiedzi.lower_bound({perm[i], i})==sasiedzi.begin())
			lewo[i][0] = {i,0};
		else{
			auto it = sasiedzi.lower_bound({perm[i], i});
			it--;
			lewo[i][0] = {(*it).second, (n+(*it).second-i)%n};
		}
		sasiedzi.erase({perm[(n+i-(k-1))%n], (n+i-(k-1))%n});
		sasiedzi.insert({perm[i], i});
	}


	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
0 / 5.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 45 ms 5712 KB Output is correct
4 Correct 39 ms 5712 KB Output is correct
5 Incorrect 40 ms 5716 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5716 KB Output is correct
2 Correct 38 ms 5716 KB Output is correct
3 Correct 39 ms 5704 KB Output is correct
4 Correct 38 ms 5716 KB Output is correct
5 Correct 38 ms 5724 KB Output is correct
6 Correct 41 ms 8016 KB Output is correct
7 Correct 93 ms 13136 KB Output is correct
8 Correct 39 ms 5968 KB Output is correct
9 Correct 56 ms 8152 KB Output is correct
10 Correct 103 ms 13136 KB Output is correct
11 Correct 101 ms 12884 KB Output is correct
12 Correct 112 ms 13140 KB Output is correct
13 Correct 95 ms 13088 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5716 KB Output is correct
2 Correct 38 ms 5716 KB Output is correct
3 Correct 39 ms 5704 KB Output is correct
4 Correct 38 ms 5716 KB Output is correct
5 Correct 38 ms 5724 KB Output is correct
6 Correct 41 ms 8016 KB Output is correct
7 Correct 93 ms 13136 KB Output is correct
8 Correct 39 ms 5968 KB Output is correct
9 Correct 56 ms 8152 KB Output is correct
10 Correct 103 ms 13136 KB Output is correct
11 Correct 101 ms 12884 KB Output is correct
12 Correct 112 ms 13140 KB Output is correct
13 Correct 95 ms 13088 KB Output is correct
14 Correct 135 ms 21796 KB Output is correct
15 Correct 790 ms 127520 KB Output is correct
16 Correct 135 ms 24148 KB Output is correct
17 Correct 820 ms 131208 KB Output is correct
18 Correct 586 ms 129872 KB Output is correct
19 Correct 563 ms 130388 KB Output is correct
20 Correct 803 ms 134996 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5720 KB Output is correct
2 Correct 51 ms 5716 KB Output is correct
3 Incorrect 102 ms 10836 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5716 KB Output is correct
2 Correct 38 ms 5784 KB Output is correct
3 Correct 38 ms 5712 KB Output is correct
4 Incorrect 38 ms 5724 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5716 KB Output is correct
2 Correct 40 ms 5716 KB Output is correct
3 Correct 38 ms 5724 KB Output is correct
4 Incorrect 38 ms 5800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 45 ms 5712 KB Output is correct
4 Correct 39 ms 5712 KB Output is correct
5 Incorrect 40 ms 5716 KB Output isn't correct
6 Halted 0 ms 0 KB -