Submission #1024799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024799		MohamedFaresNebili	Stone Arranging 2 (JOI23_ho_t1)	C++14	0 / 100	4 ms	6784 KiB

Main

#include <bits/stdc++.h>

		using namespace std;

		int N, A[200005];
		int MN[800005], MX[800005], lazy[800005];
		vector<int> C;
		void build(int v, int l, int r) {
			if(l == r) {
				MN[v] = MX[v] = A[l];
				return;
			}
			build(v * 2, l, (l + r) / 2);
			build(v * 2 + 1, (l + r) / 2 + 1, r);
			MN[v] = min(MN[v * 2], MN[v * 2 + 1]);
			MX[v] = max(MX[v * 2], MX[v * 2 + 1]);
		}
		void prop(int v, int l, int r) {
			if(lazy[v] == -1 || l == r) return;
			MN[v * 2] = MX[v * 2] = lazy[v];
			MN[v * 2 + 1] = MX[v * 2 + 1] = lazy[v];
			lazy[v * 2] = lazy[v * 2 + 1] = lazy[v];
			lazy[v] = -1;
		}
		void update(int v, int l, int r, int lo, int hi, int val) {
			prop(v, l, r);
			if(l > hi || r < lo) return;
			if(l >= lo && r <= hi) {
				MN[v] = MX[v] = val; lazy[v] = val;
				prop(v, l, r); return;
			}
			update(v * 2, l, (l + r) / 2, lo, hi, val);
			update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
			MN[v] = min(MN[v * 2], MN[v * 2 + 1]);
			MX[v] = max(MX[v * 2], MX[v * 2 + 1]);
		}
		pair<int, int> query(int v, int l, int r, int lo, int hi) {
			if(l > hi || r < lo) return {1e9, -1e9};
			if(l >= lo && r <= hi) return {MN[v], MX[v]};
			pair<int, int> U = query(v * 2, l, (l + r) / 2, lo, hi);
			pair<int, int> V = query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
			return {min(U.first, V.first), max(U.second, V.second)};
		}

		int32_t main() {
			ios_base::sync_with_stdio(0);
			cin.tie(0); cout.tie(0);
			memset(lazy, -1, sizeof lazy);
			cin >> N;
			for(int l = 0; l < N; l++) 
				cin >> A[l];
			build(1, 0, N - 1);
			for(int l = 0; l < N; l++) {
				int lo = 0, hi = l - 1, lst = -1;
				while(lo <= hi) {
					int md = (lo + hi) / 2;
					pair<int, int> Q = query(1, 0, N - 1, md, l - 1);
					if(A[l] == 1) {
						if(Q.first == 1) lst = md, lo = md + 1;
						else hi = md - 1;
					} else {
						if(Q.second == 2) lst = md, lo = md + 1;
						else hi = md - 1;
					}
				}
				if(lst == -1) continue;
				update(1, 0, N - 1, lst + 1, l - 1, A[l]);
			}
			for(int l = 0; l < N; l++) 
				cout << query(1, 0, N - 1, l, l).first << " ";

		}

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