Submission #761870

#	Time	Username	Problem	Language	Result	Execution time	Memory
761870		IvanJ	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	214 ms	31024 KiB

Main

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5;

struct Seg {
	int pot;
	vector<int> T, L;
	
	void init(int _n) {
		pot = 1;
		while(pot < _n) pot <<= 1;
		for(int i = 0;i < (pot << 1);i++) 
			T.pb(0), L.pb(0);
	}
	
	void prop(int x) {
		if(L[x]) {
			T[x] = L[x];
			if(x < pot) 
				L[x * 2] = L[x * 2 + 1] = L[x];
			L[x] = 0;
		}
	}
	
	void update(int x, int lo, int hi, int a, int b, int v) {
		prop(x);
		if(hi < a || b < lo) return;
		if(a <= lo && hi <= b) {
			L[x] = v;
			prop(x);
			return;	
		}
		int mid = (lo + hi) / 2;
		update(x * 2, lo, mid, a, b, v);
		update(x * 2 + 1, mid + 1, hi, a, b, v);
	}
	
	int query(int x, int lo, int hi, int X) {
		prop(x);
		if(lo == hi) return T[x];
		int mid = (lo + hi) / 2;
		if(lo <= X && X <= mid) 
			return query(x * 2, lo, mid, X);
		else 
			return query(x * 2 + 1, mid + 1, hi, X);	
	}
	
	void set(int lo, int hi, int v) {
		update(1, 0, pot - 1, lo, hi, v);	
	}
	
	int get(int x) {
		return query(1, 0, pot - 1, x);	
	}
};

int n;
int a[maxn];
map<int, vector<int>> pos;

int main() {
	scanf("%d", &n);
	for(int i = 0;i < n;i++) 
		scanf("%d", a + i);
	
	Seg S;
	S.init(n);
	
	for(int i = 0;i < n;i++) {
		while(pos[a[i]].size()) {
			int x = pos[a[i]].back();
			if(S.get(x) == a[i]) {
				S.set(x, i - 1, a[i]);
				break;
			}
			pos[a[i]].pop_back();
		}
		S.set(i, i, a[i]);
		pos[a[i]].pb(i);
	}
	
	for(int i = 0;i < n;i++) 
		printf("%d\n", S.get(i));
	return 0;
}

Compilation message (stderr)

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

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