QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #736902 | #3549. 262144 Revisited | _8_8_# | 8.695652 | 38ms | 8416kb | C++23 | 1.4kb | 2024-11-12 13:52:50 | 2024-11-12 13:52:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)3e3 + 12;
int n, a[N], mx[N][N];
int solve(int l, int r) {
deque<int> deq;
for(int i = l; i <= r; i++) {
deq.push_back(a[i]);
}
int t = mx[l][r];
while((int)deq.size() > 1) {
int x = deq[0], y = deq[1];
deq.pop_front();
deq.pop_front();
if(max(x, y) < t) {
deq.push_front(max(x, y) + 1);
} else {
if(x == t && !deq.empty() && y != t) {
int z = deq[0];deq.pop_front();
y = max(y, z) + 1;
if(y > t) t++;
deq.push_front(y);
deq.push_front(x);
} else {
deq.push_front(t + 1);
t++;
}
}
}
return t;
}
void test() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 1; i <= n; i++) {
mx[i][i] = a[i];
for(int j = i + 1; j <= n; j++) {
mx[i][j] = max(mx[i][j - 1], a[j]);
}
}
ll res = 0;
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
int v = solve(i, j);
res += v;
}
}
cout << res << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
}
詳細信息
Pretests
Final Tests
Test #1:
score: 4.34783
Accepted
time: 0ms
memory: 3888kb
input:
6 1 3 1 2 1 10
output:
115
result:
ok single line: '115'
Test #2:
score: 0
Wrong Answer
time: 38ms
memory: 8416kb
input:
262144 1 1 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 8 8 8 8 8 8 8 8 8 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 14 14 14 14 14 14 14 14 14 14 14 14 14 15 16 16 16 16 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 19 19 20 20 20 20 20 20 ...
output:
2371604
result:
wrong answer 1st lines differ - expected: '666881324292484', found: '2371604'
Test #3:
score: 0
Runtime Error
input:
262144 1 9 9 9 9 11 12 13 15 21 21 22 23 23 33 34 34 39 39 42 43 46 46 46 46 46 50 50 51 51 52 55 55 56 56 59 64 66 70 70 77 79 83 88 92 97 97 98 102 108 108 112 113 114 121 121 124 126 129 131 132 138 141 141 147 147 148 152 154 155 161 162 163 165 166 166 168 169 169 169 170 175 176 177 178 183 18...
output:
result:
Test #4:
score: 0
Runtime Error
input:
262144 99996 99995 99993 99993 99990 99990 99991 99990 99988 99989 99990 99989 99988 99988 99987 99989 99988 99982 99983 99983 99984 99984 99983 99981 99981 99981 99978 99978 99977 99976 99976 99977 99971 99968 99968 99968 99967 99965 99965 99965 99964 99967 99966 99965 99963 99961 99960 99960 99964...
output:
result:
Test #5:
score: 0
Runtime Error
input:
262144 199998 199997 199998 199997 199996 199997 199996 199996 199992 199992 199988 199988 199988 199990 199986 199986 199988 199988 199984 199984 199984 199985 199986 199987 199984 199984 199984 199979 199980 199980 199982 199977 199977 199976 199975 199976 199975 199976 199977 199972 199973 199973...
output:
result:
Test #6:
score: 0
Runtime Error
input:
262144 499992 499989 499989 499988 499988 499988 499988 499989 499989 499990 499985 499985 499986 499986 499985 499984 499984 499985 499985 499985 499985 499986 499986 499985 499985 499984 499984 499984 499984 499985 499985 499986 499986 499986 499986 499985 499985 499988 499988 499989 499986 499986...
output:
result:
Test #7:
score: 0
Runtime Error
input:
262144 999991 999991 999990 999990 999991 999993 999991 999991 999991 999990 999990 999989 999989 999989 999989 999988 999988 999989 999987 999987 999987 999985 999984 999984 999986 999987 999987 999988 999988 999988 999989 999989 999989 999990 999988 999988 999989 999991 999989 999988 999985 999984...
output:
result:
Test #8:
score: 0
Runtime Error
input:
262144 1000000 999996 999991 999987 999988 999987 999988 999988 999986 999985 999986 999986 999984 999982 999983 999985 999984 999982 999981 999981 999979 999978 999977 999975 999974 999975 999974 999973 999974 999971 999972 999972 999972 999973 999971 999970 999970 999965 999964 999956 999957 99995...
output:
result:
Test #9:
score: 0
Runtime Error
input:
262144 999997 999998 999996 999992 999992 999994 999989 999986 999985 999985 999985 999987 999984 999982 999982 999982 999984 999984 999981 999979 999980 999976 999976 999976 999976 999974 999974 999975 999974 999973 999974 999968 999968 999965 999965 999967 999965 999965 999960 999960 999959 999959...
output:
result:
Test #10:
score: 0
Runtime Error
input:
262144 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1...
output:
result:
Test #11:
score: 0
Runtime Error
input:
262144 518701 585574 345076 642315 75617 893688 485383 696337 31086 682159 969846 943380 254864 406197 509965 126319 135623 147440 7593 120839 163643 128819 324108 935846 334903 804212 668986 900274 503397 603547 238961 51946 697501 412370 426586 80682 390652 730017 13011 254438 357154 142380 587176...
output:
result:
Test #12:
score: 4.34783
Accepted
time: 23ms
memory: 8300kb
input:
300 216080 283804 812393 874518 459351 285947 246394 558391 105329 831354 487737 667446 725110 860965 686619 499108 856557 662571 474888 145951 754627 969797 89658 936887 391068 461211 376147 310350 185753 576410 821006 745593 39979 592437 80465 176087 47907 190517 291417 351610 276193 277438 392732...
output:
43964210127
result:
ok single line: '43964210127'
Test #13:
score: 0
Runtime Error
input:
262144 1000000 999999 999998 999997 999996 999995 999994 999993 999992 999991 999990 999989 999988 999987 999986 999985 999984 999983 999982 999981 999980 999979 999978 999977 999976 999975 999974 999973 999972 999971 999970 999969 999968 999967 999966 999965 999964 999963 999962 999961 999960 99995...
output:
result:
Test #14:
score: 0
Runtime Error
input:
262144 999996 999994 999992 999988 999984 999979 999979 999977 999975 999974 999974 999972 999972 999970 999966 999964 999960 999960 999958 999958 999956 999954 999953 999951 999947 999947 999944 999942 999942 999939 999938 999936 999932 999929 999927 999926 999924 999923 999921 999920 999917 999916...
output:
result:
Test #15:
score: 0
Runtime Error
input:
262144 999999 999999 1000000 999999 999999 1000000 999999 999999 1000000 999999 999999 1000000 999999 999999 1000000 999999 999999 1000000 999999 999999 1000000 999999 999999 1000000 999999 999999 1000000 999999 999999 1000000 999999 999999 1000000 999999 999999 1000000 999999 999999 1000000 999999 ...
output:
result:
Test #16:
score: 0
Runtime Error
input:
262144 13108 13108 13108 13107 13108 13107 13107 13107 13107 13107 13107 13108 13108 13107 13106 13106 13107 13106 13107 13106 13107 13106 13107 13106 13106 13105 13105 13105 13106 13106 13106 13106 13105 13105 13104 13104 13104 13105 13105 13105 13105 13105 13104 13103 13104 13103 13104 13103 13104...
output:
result:
Test #17:
score: 0
Wrong Answer
time: 28ms
memory: 8112kb
input:
300 999994 999993 999992 999992 999994 999993 999993 999994 999993 999993 999994 999994 999989 999989 999987 999987 999988 999988 999988 999989 999988 999987 999987 999988 999988 999988 999988 999991 999990 999990 999991 999991 999988 999988 999987 999987 999987 999987 999990 999988 999988 999988 99...
output:
44825489028
result:
wrong answer 1st lines differ - expected: '44825213269', found: '44825489028'
Test #18:
score: 0
Time Limit Exceeded
input:
3000 913347 411708 830707 139908 468414 282707 863947 767999 450119 677303 995373 830927 170138 485956 92253 450159 17536 876709 396157 624566 138039 747050 536096 755345 809347 388938 533086 633605 903211 209505 775942 150544 645398 777384 784526 972509 651132 777038 644255 300305 83761 999139 1441...
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
3000 999988 999988 999989 999990 999991 999990 999989 999987 999986 999986 999987 999986 999985 999985 999990 999990 999990 999990 999990 999990 999991 999988 999988 999989 999990 999988 999987 999986 999985 999985 999989 999988 999987 999985 999985 999986 999988 999987 999986 999986 999986 999986 9...
output:
result:
Test #20:
score: 0
Wrong Answer
time: 1ms
memory: 3856kb
input:
262144 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 8 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1...
output:
14
result:
wrong answer 1st lines differ - expected: '735361899011', found: '14'
Test #21:
score: 0
Wrong Answer
time: 0ms
memory: 3652kb
input:
262144 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 4 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 4 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 5 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 4 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 4 1 1 2 1 1 2 1 1 3 1 1 2...
output:
4
result:
wrong answer 1st lines differ - expected: '639147161394', found: '4'
Test #22:
score: 0
Wrong Answer
time: 1ms
memory: 3584kb
input:
262144 1 1 1 1 3 1 1 1 1 3 1 1 1 1 3 1 1 1 1 3 1 1 1 1 5 1 1 1 1 3 1 1 1 1 3 1 1 1 1 3 1 1 1 1 3 1 1 1 1 5 1 1 1 1 3 1 1 1 1 3 1 1 1 1 3 1 1 1 1 3 1 1 1 1 5 1 1 1 1 3 1 1 1 1 3 1 1 1 1 3 1 1 1 1 3 1 1 1 1 5 1 1 1 1 3 1 1 1 1 3 1 1 1 1 3 1 1 1 1 3 1 1 1 1 7 1 1 1 1 3 1 1 1 1 3 1 1 1 1 3 1 1 1 1 3 1 1...
output:
1
result:
wrong answer 1st lines differ - expected: '669252819258', found: '1'
Test #23:
score: 0
Time Limit Exceeded
input:
262144 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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...