Submission #1125147

#TimeUsernameProblemLanguageResultExecution timeMemory
1125147omar1312Stone Arranging 2 (JOI23_ho_t1)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; #define ll long long #define pb push_back #define all(x) x.begin(), x.end() const int mod = 1000000007; const int N = 200005; ll a[N+2], dp[N+2], col[N+2]; void solve(){ int n; cin>>n; for(int i = 0; i < n; i++){ cin>>a[i]; col[i] = a[i]; } stack<array<ll, 2>> s; map<ll, ll> mp; vector<array<ll, 2>> v; for(int i = 0; i < n; i++){ if(mp[a[i]]){ mp[a[i]]--; while(s.top()[1] != a[i]){ mp[s.top()[1]]--; s.pop(); } v.pb({-i, s.top()[0]}); s.pop(); } else{ mp[a[i]]++; s.push({i, a[i]}); } } // for(auto[i, j] : v){ // cout<<j<<' '<<-i<<'\n'; // } sort(all(v)); ll lst = -mod; while(1){ array<ll, 2> tmp1000 = {lst, -mod}; auto it = lower_bound(all(v), tmp1000); if(it == v.end())break; array<ll, 2> cur = *it; lst = cur[0] + 1; array<ll, 2> tmp = {-cur[0], cur[1]}; for(int i = tmp[1]; i <= tmp[0]; i++){ col[i] = col[tmp[1]]; } } for(int i = 0; i < n; i++){ cout<<col[i]<<' '; } } int main(){ cin.tie(0)->sync_with_stdio(0); int tt = 1; //cin>>tt; while(tt--){ solve(); cout<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...