QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#62451 | #5035. foo~ | AFewSuns | 0 | 7ms | 16440kb | C++14 | 2.8kb | 2022-11-18 22:30:02 | 2022-11-18 22:30:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 1e18
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
ll n,k,a[600060],b[600060],st[600060],top=0,ans=0;
ll f[600060],g[600060],pre[600060],suf[600060],maxx1[600060],maxx2[600060];
int main(){
// freopen("1.in","r",stdin);
// freopen("wa.out","w",stdout);
n=read();
k=read();
fr(i,1,n) a[i]=read();
ll pos=1;
fr(i,1,n) if(a[i]==n) pos=i;
fr(i,1,n) b[i]=a[(pos+i-2)%n+1];
fr(i,1,n) a[i]=b[i];
fr(i,0,n) f[i]=-inf;
f[0]=0;
fr(_,1,k){
fr(i,0,n){
g[i]=f[i];
f[i]=-inf;
}
top=0;
fr(i,1,n){
pre[i]=suf[i]=maxx1[i]=maxx2[i]=0;
pre[i]=suf[i]=g[i-1]+1;
while(top&&a[st[top]]<a[i]){
pre[i]=max(pre[i],pre[st[top]]+1);
f[i]=max(f[i],suf[st[top]]);
top--;
}
if(top){
suf[i]=max(suf[i],maxx2[st[top]]+1);
f[i]=max(f[i],maxx1[st[top]]);
}
f[i]=max(f[i],max(pre[i],suf[i]));
maxx1[i]=max(maxx1[st[top]],f[i]);
maxx2[i]=max(maxx2[st[top]],suf[i]);
st[++top]=i;
}
}
ans=f[n];
reverse(a+2,a+n+1);
fr(i,0,n) f[i]=-inf;
f[0]=0;
fr(_,1,k){
fr(i,0,n){
g[i]=f[i];
f[i]=-inf;
}
top=0;
fr(i,1,n){
pre[i]=suf[i]=maxx1[i]=maxx2[i]=0;
pre[i]=suf[i]=g[i-1]+1;
while(top&&a[st[top]]<a[i]){
pre[i]=max(pre[i],pre[st[top]]+1);
f[i]=max(f[i],suf[st[top]]);
top--;
}
if(top){
suf[i]=max(suf[i],maxx2[st[top]]+1);
f[i]=max(f[i],maxx1[st[top]]);
}
f[i]=max(f[i],max(pre[i],suf[i]));
maxx1[i]=max(maxx1[st[top]],f[i]);
maxx2[i]=max(maxx2[st[top]],suf[i]);
st[++top]=i;
}
}
write(max(ans,f[n]));
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 1ms
memory: 13652kb
input:
23 6 16 20 22 4 21 10 3 7 5 8 15 12 9 1 6 17 23 13 11 19 18 14 2
output:
20
result:
ok "20"
Test #2:
score: 0
Accepted
time: 4ms
memory: 13740kb
input:
13 6 13 9 3 4 12 6 5 1 8 10 11 7 2
output:
13
result:
ok "13"
Test #3:
score: 0
Accepted
time: 2ms
memory: 13544kb
input:
25 3 25 2 3 19 5 6 7 11 8 10 9 20 4 14 21 1 17 12 13 18 15 22 23 16 24
output:
16
result:
ok "16"
Test #4:
score: 0
Accepted
time: 4ms
memory: 13744kb
input:
25 9 1 11 10 23 9 24 7 8 19 3 5 21 18 12 15 16 17 13 2 20 14 22 4 6 25
output:
23
result:
ok "23"
Test #5:
score: 0
Accepted
time: 4ms
memory: 13648kb
input:
13 2 1 4 2 3 5 6 7 8 9 10 12 11 13
output:
12
result:
ok "12"
Test #6:
score: 0
Accepted
time: 0ms
memory: 13644kb
input:
17 5 4 2 3 6 5 1 7 8 13 16 11 12 9 14 15 10 17
output:
15
result:
ok "15"
Test #7:
score: 0
Accepted
time: 2ms
memory: 13652kb
input:
8 2 1 2 5 6 3 4 7 8
output:
8
result:
ok "8"
Test #8:
score: 0
Accepted
time: 1ms
memory: 13568kb
input:
11 5 3 11 2 10 6 5 1 4 8 7 9
output:
11
result:
ok "11"
Test #9:
score: 0
Accepted
time: 0ms
memory: 13632kb
input:
10 1 5 3 4 1 10 8 9 6 7 2
output:
6
result:
ok "6"
Test #10:
score: 0
Accepted
time: 0ms
memory: 13540kb
input:
16 2 15 12 14 9 11 13 1 3 10 8 5 2 16 4 6 7
output:
9
result:
ok "9"
Test #11:
score: 0
Accepted
time: 4ms
memory: 13584kb
input:
6 3 4 1 5 6 2 3
output:
6
result:
ok "6"
Test #12:
score: 0
Accepted
time: 3ms
memory: 13572kb
input:
1 1 1
output:
1
result:
ok "1"
Test #13:
score: 0
Accepted
time: 4ms
memory: 13740kb
input:
16 5 7 14 13 16 10 1 9 11 3 8 2 4 5 15 12 6
output:
14
result:
ok "14"
Test #14:
score: 0
Accepted
time: 2ms
memory: 13512kb
input:
10 3 10 1 7 2 8 6 9 5 4 3
output:
9
result:
ok "9"
Test #15:
score: 0
Accepted
time: 2ms
memory: 13584kb
input:
23 9 12 11 22 2 5 9 1 4 18 19 17 16 23 20 6 13 8 21 10 7 14 15 3
output:
23
result:
ok "23"
Test #16:
score: 0
Accepted
time: 4ms
memory: 13676kb
input:
15 4 4 3 8 13 12 1 14 9 15 10 7 11 2 6 5
output:
13
result:
ok "13"
Test #17:
score: 0
Accepted
time: 1ms
memory: 13744kb
input:
24 7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
output:
24
result:
ok "24"
Test #18:
score: 0
Accepted
time: 1ms
memory: 13744kb
input:
4 2 1 2 3 4
output:
4
result:
ok "4"
Test #19:
score: -10
Wrong Answer
time: 4ms
memory: 13636kb
input:
18 1 1 3 5 7 9 11 13 15 17 18 16 14 12 10 8 6 4 2
output:
4
result:
wrong answer 1st words differ - expected: '10', found: '4'
Subtask #2:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 7ms
memory: 16440kb
input:
93943 1 87243 48984 50611 19218 77699 25025 85769 28141 13380 34875 42459 66419 53472 4367 48292 16894 92171 87263 42527 67085 30687 29235 27515 81053 31421 34864 83591 70491 75344 7026 50250 63402 26773 5330 36308 76399 80032 15501 16205 71750 73964 67876 68901 70548 2043 79979 89479 19784 38838 44...
output:
20
result:
wrong answer 1st words differ - expected: '25', found: '20'
Subtask #3:
score: 0
Wrong Answer
Test #36:
score: 20
Accepted
time: 2ms
memory: 13612kb
input:
1992 25 144 612 1315 1966 1779 1773 1529 625 36 1849 1783 1441 1388 1558 1258 724 137 397 542 353 1162 1213 406 792 1317 882 994 298 1864 1969 103 449 508 1501 89 1721 195 778 657 222 1152 1780 613 743 1206 694 829 142 69 1973 1465 1343 655 1540 155 146 350 491 759 1695 1082 1357 1329 1745 232 1850 ...
output:
237
result:
ok "237"
Test #37:
score: -20
Wrong Answer
time: 4ms
memory: 13608kb
input:
1992 17 785 891 1027 155 773 587 1829 255 1239 1893 1854 158 349 370 1134 1739 1186 11 1099 1149 481 361 1101 1359 1773 1568 157 1011 79 555 254 285 1260 1722 1684 577 1054 1932 590 1804 414 1415 376 1699 26 971 1554 1504 1987 1327 1184 610 652 1432 206 129 315 1390 1946 64 910 962 1189 326 497 1580...
output:
173
result:
wrong answer 1st words differ - expected: '172', found: '173'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #2:
0%