oj.uz

Submission #917212

# Submission time Handle Problem Language Result Execution time Memory
917212 2024-01-27T12:52:31 Z jamjanek Seesaw (JOI22_seesaw) C++14
100 / 100
 1047 ms 45160 KB 
#include<bits/stdc++.h>
using namespace std;
int A[200010];
long long sumy[200010];

struct node{
	long double srodek;
	int l, r;
	bool zapalony;
};
vector<node>tab[200010];

const int base = 1<<18;
bool tree[2*base][2][2];

void update(int x){
	x/=2;
	while(x>0){
		tree[x][0][0] = (tree[x*2][0][0]&tree[x*2+1][0][0])|(tree[x*2][0][1]&tree[x*2+1][1][0]);
		tree[x][0][1] = (tree[x*2][0][0]&tree[x*2+1][0][1])|(tree[x*2][0][1]&tree[x*2+1][1][1]);
		tree[x][1][0] = (tree[x*2][1][0]&tree[x*2+1][0][0])|(tree[x*2][1][1]&tree[x*2+1][1][0]);
		tree[x][1][1] = (tree[x*2][1][0]&tree[x*2+1][0][1])|(tree[x*2][1][1]&tree[x*2+1][1][1]);
		x/=2;
	}
}

void dodaj(int i, int j){
	tab[i][j].zapalony = 1;
	auto &ja = tab[i][j];
	for(int a=0;a<(int)tab[i-1].size();a++){
		auto &pop = tab[i-1][a];
		if(abs(pop.l-ja.l)+abs(pop.r-ja.r)==1 && pop.zapalony){
			tree[base+i-1][a][j] = 1;
			update(base+i-1);
		}
	}
	for(int a=0;a<(int)tab[i+1].size();a++){
		auto &pop = tab[i+1][a];
		if(abs(pop.l-ja.l)+abs(pop.r-ja.r)==1 && pop.zapalony){
			tree[base+i][j][a] = 1;
			update(base+i);
		}
	}
	
}

void usun(int i, int j){
	tab[i][j].zapalony = 0;
	auto &ja = tab[i][j];
	for(int a=0;a<(int)tab[i-1].size();a++){
		auto &pop = tab[i-1][a];
		if(abs(pop.l-ja.l)+abs(pop.r-ja.r)==1){
			tree[base+i-1][a][j] = 0;
			update(base+i-1);
		}
	}
	for(int a=0;a<(int)tab[i+1].size();a++){
		auto &pop = tab[i+1][a];
		if(abs(pop.l-ja.l)+abs(pop.r-ja.r)==1){
			tree[base+i][j][a] = 0;
			update(base+i);
		}
	}
}
vector<vector<bool>>pom;

void zapytaj(int w, int l, int p, int a, int b){
	if(l>b || p<a)return;
	if(a<=l && p<=b){
		pom.push_back({tree[w][0][0], tree[w][0][1], tree[w][1][0], tree[w][1][1]});
		return;
	}
	zapytaj(w*2, l, (l+p)/2, a, b);
	zapytaj(w*2+1, (l+p)/2+1, p, a, b);
}

bool Da_sie(int l, int r){
	pom.clear();
	zapytaj(1, 0, base-1, l, r);
	for(int i=1;i<(int)pom.size();i++){
		vector<bool>nast={0,0,0,0};
		nast[0] = (pom[0][0]&pom[i][0])|(pom[0][1]&pom[i][2]);
		nast[1] = (pom[0][0]&pom[i][1])|(pom[0][1]&pom[i][3]);
		nast[2] = (pom[0][2]&pom[i][0])|(pom[0][3]&pom[i][2]);
		nast[3] = (pom[0][2]&pom[i][1])|(pom[0][3]&pom[i][3]);
		pom[0] = nast;
	}
	return pom[0][0]|pom[0][1]|pom[0][2]|pom[0][3];
}

int main()
{
	int n, i;
	scanf("%d", &n);
	for(i=1;i<=n;i++){
		scanf("%d", &A[i]);
		sumy[i]=sumy[i-1]+A[i];
	}
	long double srodek = (long double)sumy[n]/n;
	tab[n].push_back({srodek, 1, n});
	for(i=n;i>1;i--){
		vector<node>kolejna;
		for(auto j: tab[i]){
			kolejna.push_back({ ((long double)sumy[j.r-1]-sumy[j.l-1])/(j.r-j.l), j.l, j.r-1});
			kolejna.push_back({ ((long double)sumy[j.r]-sumy[j.l])/(j.r-j.l), j.l+1, j.r});
		}
		while(kolejna.size()>=2 && kolejna[kolejna.size()-2].srodek>=srodek)kolejna.pop_back();
		reverse(kolejna.begin(), kolejna.end());
		while(kolejna.size()>=2 && kolejna[kolejna.size()-2].srodek<=srodek)kolejna.pop_back();
		reverse(kolejna.begin(), kolejna.end());
		tab[i-1] = kolejna;
	}
	/*
	for(i=1;i<=n;i++){
		printf("%d:\n", i);
		for(auto j: tab[i])
			printf("%Lf %d %d\n", j.srodek, j.l, j.r);
	}*/
	vector<pair<long double, pair<int,int>>>sorted;
	for(i=1;i<=n;i++)
		for(int j=0;j<(int)tab[i].size();j++)
			sorted.push_back({tab[i][j].srodek, {i, j}});
	sort(sorted.begin(), sorted.end());
//	for(auto j: sorted)printf("{%Lf %d %d}, ", j.first, j.second.first, j.second.second);printf("\n");
	dodaj(sorted[0].second.first, sorted[0].second.second);
	int L=0, R=0;
	long double wynik = 1000000000;
	while(R<(int)sorted.size()){
//		printf("L=%d R=%d, %d\n", L, R, (int)Da_sie(0, n-2));
//		for(i=0;i<4;i++)printf("%d %d %d %d      ", (int)tree[base+i][0][0], (int)tree[base+i][0][1], (int)tree[base+i][1][0], (int)tree[base+i][1][1]);printf("\n");
		if(Da_sie(1, n-1)){
			wynik = min(wynik, sorted[R].first-sorted[L].first);
			usun(sorted[L].second.first, sorted[L].second.second);
			L++;
		}
		else{
			R++;
			if(R==(int)sorted.size())break;
			dodaj(sorted[R].second.first, sorted[R].second.second);
		}
	}
	printf("%Lf\n", wynik);
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
seesaw.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d", &A[i]);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8648 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8648 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8648 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 9 ms 9048 KB Output is correct
9 Correct 11 ms 9052 KB Output is correct
10 Correct 11 ms 9052 KB Output is correct
11 Correct 9 ms 8888 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8648 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 9 ms 9048 KB Output is correct
9 Correct 11 ms 9052 KB Output is correct
10 Correct 11 ms 9052 KB Output is correct
11 Correct 9 ms 8888 KB Output is correct
12 Correct 1047 ms 44616 KB Output is correct
13 Correct 994 ms 45160 KB Output is correct
14 Correct 1028 ms 44476 KB Output is correct
15 Correct 1010 ms 44224 KB Output is correct
16 Correct 1041 ms 43964 KB Output is correct