Submission #1004986

#TimeUsernameProblemLanguageResultExecution timeMemory
1004986underwaterkillerwhaleStone Arranging 2 (JOI23_ho_t1)C++17
100 / 100
134 ms36420 KiB
//#ifdef ONLINE_JUDGE // #include "cyberland.h" //#endif #include <bits/stdc++.h> #define se second #define fs first #define mp make_pair #define pb push_back #define ll long long #define ii pair<ll,ll> #define ld long double #define SZ(v) (int)v.size() #define ALL(v) v.begin(), v.end() #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) using namespace std; mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count()); ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); } const int N = 2e5 + 2; const ll Mod = 998244353; const int szBL = 50; const int INF = 1e9 + 7; const int BASE = 137; int n; int a[N], c[N]; set<pair<int,int>> sIT[N]; vector<int> zip; void compress() { rep (i, 1, n) zip.push_back(a[i]); sort (ALL(zip)); zip.resize(unique(ALL(zip)) - zip.begin()); rep (i ,1, n) { a[i] = lower_bound(ALL(zip), a[i]) - zip.begin(); } } void solution() { cin >> n; rep (i, 1, n) { cin >> a[i]; } compress(); set<pair<int, int>> IT; rep (i, 1, n) { if (sIT[a[i]].empty()) sIT[a[i]].insert(mp(i, i)), IT.insert(mp(i, i)); else { pair<int,int> lstIT = *prev(sIT[a[i]].end()); auto it = IT.lower_bound(lstIT); static vector<pair<int,int>> vecdel; vecdel.clear(); for (auto it = IT.lower_bound(lstIT); it != IT.end(); ++it) { pair<int,int> curIT = *it; int curcol = a[curIT.se]; sIT[curcol].erase(sIT[curcol].find(curIT)); vecdel.push_back(curIT); } iter (&itv, vecdel) IT.erase(IT.find(itv)); IT.insert(mp(lstIT.fs, i)); sIT[a[i]].insert(mp(lstIT.fs, i)); } } rep (i ,1, n) { auto it = IT.upper_bound(mp(i, INF)); --it; cout << zip[a[it->se]] <<" "; } } #define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); int main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // file ("PAINT"); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* 7 1 2 3 1 2 1 3 1 4 4 30 3 1 1 2 1 0 1 5 0 2 5 1 3 2 2 3 4 3 2 0 1 5 0 2 5 1 1 2 */

Compilation message (stderr)

Main.cpp: In function 'void solution()':
Main.cpp:54:18: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   54 |             auto it = IT.lower_bound(lstIT);
      |                  ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...