Submission #895511

#TimeUsernameProblemLanguageResultExecution timeMemory
895511LiuBruhStone Arranging 2 (JOI23_ho_t1)C++17
60 / 100
2032 ms37180 KiB
#include <bits/stdc++.h> #define int long long #define sz(v) (int)v.size() using namespace std; const int maxn = (int)2e5 + 5; const int INF = (int)1e18 + 5; int n; int ar[maxn]; set<int> st[maxn]; map<int, int> revans; void hehe() { vector<int> tmp; for (int i = 1; i <= n; i++) { tmp.push_back(ar[i]); } sort(tmp.begin(), tmp.end()); tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin()); for (int i = 1; i <= n; i++) { int x = lower_bound(tmp.begin(), tmp.end(), ar[i]) - tmp.begin() + 1; revans[x] = ar[i]; ar[i] = x; } } void solve() { cin >> n; for (int i = 1; i <= n; i++) cin >> ar[i]; hehe(); for (int i = 1; i <= n; i++) { int x = ar[i]; if (sz(st[x]) != 0) { for (int j = *st[x].rbegin(); j <= i; j++) { st[ar[j]].erase(j); st[x].insert(j); ar[j] = x; } } st[x].insert(i); } for (int i = 1; i <= n; i++) { cout << revans[ar[i]] << '\n'; } } /* 6 1 2 1 2 3 2 10 1 1 2 2 1 2 2 1 1 2 */ signed main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...