제출 #1144740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144740		fabijan_cikac	Stone Arranging 2 (JOI23_ho_t1)	C++20	0 / 100	7 ms	724 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define pp pair<int, int>
#define F first
#define S second
#define pb push_back

const int N = 4 * 1e5 + 1000;
const int B = 450;

int n, a[N];
set<int> s[N / B];
int prop[N / B];

void def(){
	memset(prop, -1, sizeof(prop));
	for (int i = 0; i < N / B; ++i)
		s[i].insert(0);
}

void propagate(int x){
	if (prop[x] == -1) return;
	for (int i = x * B; i < min(N, (x + 1) * B); ++i) a[i] = prop[x];
	s[x].clear(); s[x].insert(prop[x]); prop[x] = -1;
}

int bk(int x){ return (x / B); }

bool found(int x, int y){
	return (s[y].find(x) != s[y].end());
}

//reval blok
void reval(int x){
	propagate(x); s[x].clear();
	for (int i = x * B; i < min(N, (x + 1) * B); ++i)
		s[x].insert(a[i]);
}

void uprop(int x, int y){
	prop[x] = y; s[x].clear(); s[x].insert(y);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n; def();
	for (int i = 0; i < n; ++i){
		int x; cin >> x; int y = bk(i);
		
		while (y >= 0 && !found(x, y)) --y;
		
		//if (!s[3].empty()) cout << (*s[3].begin()) << endl;
		//cout << "! " << i << ' ' << y << endl;
		if (y == bk(x)){
			//cout << "a " << i << ' ' << y << endl;
			propagate(y);
			
			int z = i;
			while (a[z] != x) --z;
			while (z <= i) a[z++]=x;
			reval(y);
		}
		else if (y >= 0){
			//cout << "b " << i << ' ' << y << endl;
			propagate(y);
			
			int z = (y + 1) * B - 1;
			while (a[z] != x) --z;
			//cout << " -> " << z << endl;
			while (z < (y + 1) * B) a[z++]=x;
			reval(y);
			
			for (int j = bk(z); j < bk(i); ++j) uprop(j, x);
			
			for (int j = bk(i) * B; j <= i; ++j) a[j] = x;
			reval(bk(i));
		}
		else{
			//cout << "c " << i << ' ' << bk(i) << endl;
			propagate(bk(i));
			a[i] = x; reval(bk(i));
		}
	}
	
	for (int i = 0; i < N / B; ++i)
		propagate(i);
	for (int i = 0; i < n; ++i)
		cout << a[i] << '\n';
	
	return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40