Submission #1024801

#TimeUsernameProblemLanguageResultExecution timeMemory
1024801MohamedFaresNebiliStone Arranging 2 (JOI23_ho_t1)C++14
35 / 100
1062 ms10324 KiB
#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) { prop(v, l, r); 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 << " "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...