| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 72130 |
2018-08-26T05:26:45 Z |
@younha_holic(#2227, jun6873, rkm0959) |
Box Run (FXCUP3_box) |
C++17 |
|
1000 ms |
868 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1<<19;
int n, a[maxn], b[maxn];
typedef pair<int, int> pint;
#define x first
#define y second
pint dq[maxn];
int y, z;
void xfill(int s, int e, int l, int r) {
if (s>e) return;
int m = (s+e)/2, k = max(m, l);
y = 0, z = 0;
for (int i=k-m+1; i<=k; i++) {
while (y<z and dq[z-1].x < a[i]) z--;
dq[z++] = pint(a[i], i);
}
while (k+1<=r) {
pint x = dq[y];
if (a[k+1] > x.x) break;
k++;
if (dq[y].y < k-m+1) y++;
while (y<z and dq[z-1].x < a[k]) z--;
dq[z++] = pint(a[k], k);
}
if (k>r) k = r;
b[m] = k;
if (s<e) {
int m = (s+e)/2;
xfill(s, m-1, l, k);
xfill(m+1, e, k, r);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i=1; i<=n; i++) cin >> a[i];
xfill(1, n, 1, n);
for (int i=1; i<=n; i++) {
if (b[i] == n) cout << -1 << ' ';
else cout << b[i] - i + 1 << ' ';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
412 KB |
Output is correct |
| 4 |
Correct |
3 ms |
540 KB |
Output is correct |
| 5 |
Correct |
3 ms |
620 KB |
Output is correct |
| 6 |
Correct |
3 ms |
620 KB |
Output is correct |
| 7 |
Correct |
2 ms |
620 KB |
Output is correct |
| 8 |
Correct |
2 ms |
620 KB |
Output is correct |
| 9 |
Correct |
4 ms |
620 KB |
Output is correct |
| 10 |
Correct |
3 ms |
620 KB |
Output is correct |
| 11 |
Correct |
2 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
412 KB |
Output is correct |
| 4 |
Correct |
3 ms |
540 KB |
Output is correct |
| 5 |
Correct |
3 ms |
620 KB |
Output is correct |
| 6 |
Correct |
3 ms |
620 KB |
Output is correct |
| 7 |
Correct |
2 ms |
620 KB |
Output is correct |
| 8 |
Correct |
2 ms |
620 KB |
Output is correct |
| 9 |
Correct |
4 ms |
620 KB |
Output is correct |
| 10 |
Correct |
3 ms |
620 KB |
Output is correct |
| 11 |
Correct |
2 ms |
620 KB |
Output is correct |
| 12 |
Correct |
6 ms |
620 KB |
Output is correct |
| 13 |
Correct |
35 ms |
620 KB |
Output is correct |
| 14 |
Execution timed out |
1074 ms |
868 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
