用户输出
0 2
系统信息
Exited with return code 0| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #27399 | #1151. 把你挂在地灵殿门口当装饰品！ | Accepted | 100 | 388 ms | 3864 K | C++ 17 (Clang) / 1.1 K | Komeiji Koishi | 2020-06-30 10:55:20 |
#include <cstdio>
#include <algorithm>
using namespace std;
int t, _, n, i, ppos = 0, pre = 0, ppr[200005], l, r, ll, rr, a[200005], pos[200005], dp[200005], vis[200005],
mid;
const int inf = 1e9;
bool chk(int u, int v) {
int i, pre;
pre = 0;
for (i = u; i <= n; i++) {
if (a[i] <= v)
continue;
if (a[i] < pre)
return false;
pre = a[i];
}
return true;
}
int main() {
t = 1;
for (_ = 1; _ <= t; _++) {
scanf("%d", &n);
for (i = 1; i <= n; i++) scanf("%d", &a[i]), pos[a[i]] = i, dp[i] = vis[i] = 0;
vis[n + 1] = 0;
vis[0] = 0;
dp[0] = 0;
dp[n + 1] = 0;
for (i = n; i >= 0; i--) {
if (vis[a[i] + 1])
dp[a[i]] = 1 + dp[a[i] + 1];
else
dp[a[i]] = 1;
vis[a[i]] = 1;
}
ppos = 0;
pre = 0;
ppr[0] = 0;
for (l = 1; l <= n; l++) {
// printf("%d %d\n",l,pre);
if (a[l] < pre)
goto tag;
for (pre++; pre < a[l]; pre++) {
if (pos[pre] < ppos)
goto tag;
ppos = pos[pre];
}
ppr[l] = ppos;
}
tag:
l--;
ll = 0;
rr = l + 1;
while (ll < rr) {
mid = (ll + rr) / 2;
if (mid == l + 1) {
rr = mid;
continue;
}
if (chk(mid + 1, (ppr[mid] < pos[a[mid] + 1] ? a[mid] + dp[a[mid]] - 1 : a[mid])))
rr = mid;
else
ll = mid + 1;
}
if (l < rr)
printf("-1 -1\n");
else {
printf("%d %d\n", rr, l);
}
}
return 0;
}200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
<1288805 bytes omitted>用户输出
99793 101989
系统信息
Exited with return code 0200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
<1288805 bytes omitted>用户输出
99439 102575
系统信息
Exited with return code 0200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
<1288805 bytes omitted>用户输出
99526 103431
系统信息
Exited with return code 0200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
<1288805 bytes omitted>用户输出
98873 107693
系统信息
Exited with return code 0200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
<1288805 bytes omitted>用户输出
99404 103262
系统信息
Exited with return code 0200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
<1288805 bytes omitted>用户输出
89805 90017
系统信息
Exited with return code 0200000
1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 3
<1288805 bytes omitted>用户输出
89614 90080
系统信息
Exited with return code 0200000
1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 3
<1288805 bytes omitted>用户输出
89785 90028
系统信息
Exited with return code 0200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24 25 26 27 28 30 31 32 34 35 36 37
<1288805 bytes omitted>用户输出
89789 90119
系统信息
Exited with return code 0200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
<1288805 bytes omitted>用户输出
89563 90067
系统信息
Exited with return code 0200000
1 2 4 5 7 8 9 12 13 14 16 18 19 21 22 23 25 27 29 30 33 35 38 40 41 42 43 44 47 50 51 52 53
<1288805 bytes omitted>用户输出
49769 50000
系统信息
Exited with return code 0200000
1 4 5 9 10 11 13 14 15 16 20 21 25 26 28 31 32 33 35 36 37 38 39 40 41 42 45 46 47 56 58 59
<1288805 bytes omitted>用户输出
49733 50034
系统信息
Exited with return code 0200000
1 4 5 6 7 9 10 11 16 19 20 21 22 23 29 33 38 40 41 42 43 44 49 50 51 52 54 55 57 60 61 63 64
<1288805 bytes omitted>用户输出
49924 50004
系统信息
Exited with return code 0200000
3 4 9 11 13 14 15 18 20 22 23 24 25 27 30 32 34 37 40 43 44 47 48 49 50 51 60 62 63 65 67 69
<1288805 bytes omitted>用户输出
49925 50006
系统信息
Exited with return code 0