QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#62452#5035. foo~AFewSuns20 39ms33988kbC++142.7kb2022-11-18 22:32:292022-11-18 22:32:32

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-18 22:32:32]
  • 评测
  • 测评结果:20
  • 用时:39ms
  • 内存:33988kb
  • [2022-11-18 22:32:29]
  • 提交

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(){
	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;
		}
	}
	fr(i,1,n) ans=max(ans,f[i]);
	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;
		}
	}
	fr(i,1,n) ans=max(ans,f[i]);
	write(ans);
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 13552kb

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: 2ms
memory: 13576kb

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: 0ms
memory: 9468kb

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: 0ms
memory: 11696kb

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: 3ms
memory: 11468kb

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: 3ms
memory: 11480kb

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: 0ms
memory: 11524kb

input:

8 2
1 2 5 6 3 4 7 8

output:

8

result:

ok "8"

Test #8:

score: 0
Accepted
time: 3ms
memory: 11524kb

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: 2ms
memory: 11528kb

input:

10 1
5 3 4 1 10 8 9 6 7 2

output:

6

result:

ok "6"

Test #10:

score: 0
Accepted
time: 1ms
memory: 11592kb

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: 2ms
memory: 11520kb

input:

6 3
4 1 5 6 2 3

output:

6

result:

ok "6"

Test #12:

score: 0
Accepted
time: 0ms
memory: 11520kb

input:

1 1
1

output:

1

result:

ok "1"

Test #13:

score: 0
Accepted
time: 4ms
memory: 11528kb

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: 1ms
memory: 11532kb

input:

10 3
10 1 7 2 8 6 9 5 4 3

output:

9

result:

ok "9"

Test #15:

score: 0
Accepted
time: 1ms
memory: 11516kb

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: 0ms
memory: 9564kb

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: 3ms
memory: 9572kb

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: 0ms
memory: 9492kb

input:

4 2
1 2 3 4

output:

4

result:

ok "4"

Test #19:

score: 0
Accepted
time: 2ms
memory: 9552kb

input:

18 1
1 3 5 7 9 11 13 15 17 18 16 14 12 10 8 6 4 2

output:

10

result:

ok "10"

Test #20:

score: 0
Accepted
time: 2ms
memory: 9452kb

input:

18 2
1 3 5 7 9 11 13 15 17 18 16 14 12 10 8 6 4 2

output:

18

result:

ok "18"

Subtask #2:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 6ms
memory: 14424kb

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:

25

result:

ok "25"

Test #22:

score: 0
Accepted
time: 7ms
memory: 16768kb

input:

112118 1
24338 1586 3 108269 5 53472 80391 70331 9 15335 62487 28331 13 14 16564 94323 36681 108815 32632 44382 21 22 23 24 11758 40070 21518 51991 109983 30 45524 59784 33 2068 62111 36 37 38 39 89031 30508 42 43 16414 110006 34303 47 10331 44651 50 93957 95407 22019 88681 56605 12426 28498 58 59 8...

output:

281

result:

ok "281"

Test #23:

score: 0
Accepted
time: 28ms
memory: 31912kb

input:

391400 1
158965 280194 3 4 5 369036 92293 245923 57403 10 6887 280754 277300 110148 314164 135940 17 46573 126951 111447 301107 22 23 24 25 26 247952 28 342994 339309 23647 350245 33 299608 35 36 37 263236 232063 40 41 42 43 44 39280 46 299122 11961 380375 384513 51 318009 162567 54 55 56 27356 58 6...

output:

693

result:

ok "693"

Test #24:

score: 0
Accepted
time: 31ms
memory: 33016kb

input:

440571 1
243784 2 3 130039 61385 6 7 8 244611 260729 29014 12 326371 416098 15 293728 182717 66822 387603 156910 225815 413135 171756 315815 26444 302419 384825 37746 17634 391896 354575 426625 290920 34 49456 36 161212 212843 39 40 41 436888 43 102088 405279 46 47 77451 49 50 368530 52402 34143 54 ...

output:

665

result:

ok "665"

Test #25:

score: 0
Accepted
time: 17ms
memory: 22664kb

input:

237580 1
1 2 3 4 5 45736 171997 8 235046 10 11 186778 13 14 15 16 17 18 19 20 21 22 23 91724 25 147783 27 125261 29 30 27556 32 108919 76675 35 36 18966 212471 100584 11715 204252 77843 43 176763 18552 46 82644 48 49 50 51 191552 53 232631 160703 114013 69672 75193 59 60 207114 62 63 167312 83372 66...

output:

890

result:

ok "890"

Test #26:

score: 0
Accepted
time: 0ms
memory: 14944kb

input:

108629 1
1 2 3 35575 5 7205 104276 8 9 10 104552 12 13 99818 15 16 17 18 19 16579 21 74459 23 24 25 98758 27 30553 28622 105401 31 32 33 98277 29214 36 37 38 34671 99851 41 42 20159 65626 49334 58829 47 48 15553 50 16448 157 96610 71139 51449 24593 66195 11741 5738 45685 61 76006 91433 64 13205 66 6...

output:

549

result:

ok "549"

Test #27:

score: 0
Accepted
time: 3ms
memory: 11756kb

input:

7474 1
6087 2 3 3276 2246 1022 4790 8 9 10 11 3555 13 14 5187 16 17 18 5222 2852 21 3905 23 2069 25 26 27 6248 29 30 31 32 33 3467 35 5413 37 38 39 40 41 42 43 44 45 46 47 6366 6217 6683 4855 86 6754 7423 55 56 3421 58 7129 6415 2719 964 63 7191 6681 5871 2830 68 1114 70 71 4387 73 74 75 76 77 394 7...

output:

117

result:

ok "117"

Test #28:

score: 0
Accepted
time: 27ms
memory: 28124kb

input:

327474 1
210193 138271 6815 114087 210548 236834 247829 287541 142327 57519 226037 185228 4602 111639 172642 13926 122775 323427 276201 198051 175153 262523 182602 84772 315273 161585 146845 231049 98201 170526 58890 213780 86346 161912 320369 55154 202159 224318 92082 314469 92925 225630 89586 2190...

output:

31

result:

ok "31"

Test #29:

score: 0
Accepted
time: 9ms
memory: 17492kb

input:

170736 1
1312 68283 94512 153956 14227 44793 18760 153190 59267 3745 39898 34452 88526 153153 151245 72089 72230 139449 97869 105574 61308 52310 63909 66185 76461 57922 15750 32965 63821 123214 62562 154258 26229 154847 29694 20613 163634 112566 78733 77415 148297 8311 18695 146847 137996 128167 946...

output:

27

result:

ok "27"

Test #30:

score: 0
Accepted
time: 4ms
memory: 14464kb

input:

70972 1
42126 45376 26395 39090 6557 69493 22740 10263 3057 30503 16364 27796 52951 62922 17830 66723 34385 8039 28194 11087 10500 9835 5892 8917 21894 16673 49698 55082 66683 54472 60557 6953 739 65333 59825 23918 39644 59672 59765 31158 30188 37359 60653 64449 28747 7064 53759 15156 11687 33993 33...

output:

25

result:

ok "25"

Test #31:

score: 0
Accepted
time: 39ms
memory: 33988kb

input:

471980 1
315450 386066 223827 468592 231628 77257 181339 466496 85446 27241 269600 85959 141799 29249 162311 264524 137245 205794 349273 166576 131873 5521 368496 302373 19082 283842 82343 281817 25429 161084 307699 192224 143156 188759 279732 138312 341989 400389 280646 404120 362537 182646 194306 ...

output:

32

result:

ok "32"

Test #32:

score: 0
Accepted
time: 9ms
memory: 18892kb

input:

141837 1
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...

output:

141837

result:

ok "141837"

Test #33:

score: 0
Accepted
time: 0ms
memory: 13868kb

input:

48198 1
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 ...

output:

48198

result:

ok "48198"

Test #34:

score: 0
Accepted
time: 4ms
memory: 10848kb

input:

28730 1
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173...

output:

14366

result:

ok "14366"

Test #35:

score: 0
Accepted
time: 8ms
memory: 14656kb

input:

89450 1
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173...

output:

44726

result:

ok "44726"

Subtask #3:

score: 0
Wrong Answer

Test #36:

score: 20
Accepted
time: 4ms
memory: 11652kb

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: 11700kb

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:

100%
Accepted

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #2:

100%
Accepted

Dependency #5:

0%