# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
251674 | VEGAnn | Baloni (COCI15_baloni) | C++14 | 2021 ms | 131076 KiB |
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>
#define sz(x) ((int)x.size())
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int N = 1000100;
const int C = 22;
const int md = 10007;
set<i2> st;
set<int> ps[N];
set<int>::iterator iter;
int n, a[N], ans, nt[N], pos[N];
int mult(int x, int y) { return (x * y) % md; }
void SUM(int &x, int y){
x += y;
if (x >= md)
x -= md;
}
int main() {
#ifdef _LOCAL
freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout);
#else
// freopen("mining.in","r",stdin); freopen("mining.out","w",stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = n; i > 0; i--){
nt[i] = pos[a[i] - 1];
pos[a[i]] = i;
st.insert({a[i], -i});
ps[a[i]].insert(i);
}
while (sz(st) > 0){
ans++;
i2 cr = (*(--st.end()));
st.erase(cr);
int pst = -cr[1], vl = cr[0];
while (pst != 0){
if (sz(ps[vl - 1]) == 0) break;
iter = ps[vl - 1].upper_bound(pst);
if (iter == ps[vl - 1].end()) break;
ps[vl - 1].erase(iter);
pst = *iter;
vl--;
st.erase({a[pst], -pst});
}
}
cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |