# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
512395 |
2022-01-16T10:24:21 Z |
Kaguya |
Po (COCI21_po) |
C++17 |
|
1000 ms |
7108 KB |
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3, Ofast, unroll-loops")
#pragma GCC target("avx2")
#pragma GCC target("bmi2")
vector<int> pos[100051];
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());
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>> > 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;
ans += 1;
vs.pop();
}
}
if (a[i] == x)
vis[i] = true;
i++;
}
if (a[i] == x)
vis[i] = true;
}
}
cout << ans << '\n';
}
Compilation message
Main.cpp:5:47: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
5 | #pragma GCC optimize("O3, Ofast, unroll-loops")
| ^
Main.cpp:5:47: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
6 | #pragma GCC target("avx2")
| ^
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:6:26: warning: bad option '
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
1 ms |
2636 KB |
Output is correct |
4 |
Correct |
11 ms |
3340 KB |
Output is correct |
5 |
Correct |
16 ms |
3660 KB |
Output is correct |
6 |
Execution timed out |
1092 ms |
7108 KB |
Time limit exceeded |
7 |
Correct |
27 ms |
6992 KB |
Output is correct |