# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
512371 |
2022-01-16T10:03:59 Z |
Kaguya |
Po (COCI21_po) |
C++17 |
|
1000 ms |
7132 KB |
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("-O3")
#pragma GCC optimize("-Ofast")
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
bool have = false;
for (auto& t : a) {
cin >> t;
if (t == 0)
have = true;
}
vector<int> ve;
for (int i = 0; i < n; i++)
ve.push_back(a[i]);
sort(ve.begin(), ve.end());
ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
for (int i = 0; i < n; i++) {
a[i] = lower_bound(ve.begin(), ve.end(), a[i]) - ve.begin();
}
int ans = 0;
vector<int> se;
vector<bool> vis(n, false);
vector<bool> was(n + 11, false);
for (int i = 0; i < n; i++)
if (!was[a[i]]) {
se.push_back(a[i]);
was[a[i]] = true;
}
sort(se.rbegin(), se.rend());
vector<int> pos[n + 2];
for (int i = 0; i < n; i++)
pos[a[i]].push_back(i);
if (!have) {
ans += 1;
se.pop_back();
}
for (int i = 0; i < n; i++)
if (have && a[i] == 0)
vis[i] = true;
if (have && se.back() == 0)
se.pop_back();
while (!se.empty()) {
int x = se.back();
se.pop_back();
for (auto t : pos[x]) {
if (vis[t])
continue;
vis[t] = true;
int i = t;
ans += 1;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > vs;
while (i < n && a[i] >= x) {
if (a[i] > x)
vs.push({a[i], i});
if (!vs.empty() && ((vs.top())).first < x) {
while (!vs.empty() && ((vs.top())).first < x) {
vis[((vs.top())).second] = true;
vs.pop();
}
}
if (a[i] == x)
vis[i] = true;
i++;
}
if (a[i] == x)
vis[i] = true;
}
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
11 ms |
2128 KB |
Output is correct |
5 |
Correct |
16 ms |
3148 KB |
Output is correct |
6 |
Execution timed out |
1087 ms |
7132 KB |
Time limit exceeded |
7 |
Correct |
30 ms |
6988 KB |
Output is correct |