Submission #1144780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144780		fabijan_cikac	Stone Arranging 2 (JOI23_ho_t1)	C++20	60 / 100	2092 ms	12660 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 B = 300;
const int N = ((2 * 1e5 + 100) / B) * B;

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

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());
}

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

//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);
		
		//cout << y << endl;
		while (y >= 0 && !found(x, y)) --y;
	
		//cout << i << ' ' << y << endl;
		if (y == bk(i)){
			int z = i;
			while (a[z] != x) --z;
			
			//cout << "! " << z << endl;
			while (z <= i){
				s[y].erase(s[y].find(a[z]));
				a[z] = x; s[y].insert(x);
				++z;
			}
			//cout << "ok" << endl;
		}
		else if (y >= 0){
			propagate(y);
			
			int z = (y + 1) * B - 1;
			while (a[z] != x) --z;
			while (z < (y + 1) * B){
				s[y].erase(s[y].find(a[z]));
				a[z] = x; s[y].insert(x);
				++z;
			}
			
			for (int j = bk(z); j < bk(i); ++j) uprop(j, x);
			
			for (int j = bk(i) * B; j <= i; ++j){
				s[bk(i)].erase(s[bk(i)].find(a[j]));
				a[j] = x; s[bk(i)].insert(x);
			}
		}
		else{
			s[bk(i)].erase(s[bk(i)].find(a[i]));
			a[i] = x; s[bk(i)].insert(x);
		}
	}
	
	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: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 0 / 40