Submission #1144053

#TimeUsernameProblemLanguageResultExecution timeMemory
1144053jiahngStone Arranging 2 (JOI23_ho_t1)C++20
100 / 100
69 ms13500 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef pair<int,int> pi; typedef pair<ll,ll> pill; typedef vector <int> vi; typedef vector <pi> vpi; typedef pair<pi, ll> pii; typedef set <ll> si; typedef long double ld; #define f first #define s second #define mp make_pair #define FOR(i,s,e) for(int i=s;i<=int(e);++i) #define DEC(i,s,e) for(int i=s;i>=int(e);--i) #define pb push_back #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) #define aFOR(i,x) for (auto i: x) #define mem(x,i) memset(x,i,sizeof x) #define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define INF (ll)1e18 #define MOD 1000000007 typedef pair <vi, int> pvi; typedef pair <int,pi> ipi; typedef vector <pii> vpii; typedef pair <pi,pi> pipi; #define maxn 500010 int N,A[maxn],ans[maxn],num[maxn]; int32_t main(){ fast; cin >> N; FOR(i,1,N) cin >> A[i]; vi v; FOR(i,1,N) v.pb(A[i]); sort(all(v)); FOR(i,1,N) A[i] = lbd(v, A[i]) - v.begin(); FOR(i,1,N) num[i] = 0; stack <pii> ranges; FOR(i,1,N){ if (num[A[i]] > 0){ while (ranges.top().s != A[i]){ num[ranges.top().s]--; ranges.pop(); } ranges.push(pii(pi(ranges.top().f.s+1, i), A[i])); }else ranges.push(pii(pi(i,i), A[i])); num[A[i]]++; } while (!ranges.empty()){ FOR(i,ranges.top().f.f, ranges.top().f.s) ans[i] = ranges.top().s; ranges.pop(); } FOR(i,1,N) cout << v[ans[i]] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...