This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
map<int, vector<pii> > q;
int a[201000];
void solve(){
int n;
cin>>n;
set<pair<pii, int> > d;
for(int i=1; i<=n; i++){
cin>>a[i];
if(q[a[i]].size() == 0){
q[a[i]].pb({i, i});
d.insert({{i, i}, a[i]});
continue;
}
pii h = q[a[i]].back();
//auto g = d.find({h, a[i]});
while(d.size() and (*d.rbegin()).ff >= h){
auto g = d.end();
g--;
q[g -> ss].pop_back();
d.erase(g);
}
q[a[i]].pb({h.ff, i});
d.insert({{h.ff, i}, a[i]});
}
for(auto h: d){
for(int i=h.ff.ff; i<=h.ff.ss; i++){
a[i] = h.ss;
}
}
for(int i=1; i<=n; i++){
cout<<a[i]<<'\n';
}
}
int main(){
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |