QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#662849	#7367. 群岛	wanggk	100 ✓	41ms	12072kb	C++14	2.2kb	2024-10-21 11:16:13	2024-10-21 11:16:13

Judging History

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

[2024-10-21 11:16:13]
评测

测评结果：100
用时：41ms
内存：12072kb

查看

[2024-10-21 11:16:13]
提交

answer

#include<bits/stdc++.h>
#define For(i,il,ir) for(int i=(il);i<=(ir);++i)
#define mid (l+r>>1)
using namespace std;
template<typename T>
inline void read(T& x){
	bool f=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){ if(ch=='-') f=1; ch=getchar(); }
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	if(f) x=-x;
}
template<typename T,typename... Args>
void read(T& first,Args&... args){ read(first),read(args...); }
const int maxn=1e6+10;

int n,Q;
int a[maxn];
struct node{
	int tag;
	int mn,id;
}tr[maxn<<2];
void build(int o,int l,int r){
	tr[o].tag=tr[o].mn=0,tr[o].id=r;
	if(l==r) return;
	build(o<<1,l,mid),build(o<<1|1,mid+1,r);
}
int upx,upy,upz;
void upd(int o,int addv){ tr[o].mn+=addv,tr[o].tag+=addv; }
void pushdown(int o){ upd(o<<1,tr[o].tag),upd(o<<1|1,tr[o].tag),tr[o].tag=0; }
void update(int o,int l,int r){
	if(upx<=l&&r<=upy){ upd(o,upz); return; }
	if(tr[o].tag) pushdown(o);
	if(upx<=mid) update(o<<1,l,mid);
	if(upy>mid) update(o<<1|1,mid+1,r);
	
	if(tr[o<<1].mn>=tr[o<<1|1].mn) tr[o].mn=tr[o<<1|1].mn,tr[o].id=tr[o<<1|1].id;
	else tr[o].mn=tr[o<<1].mn,tr[o].id=tr[o<<1].id;
}
int qx,qy;
node query(int o,int l,int r){
	if(qx<=l&&r<=qy) return tr[o];
	if(tr[o].tag) pushdown(o);
	if(qy<=mid) return query(o<<1,l,mid);
	if(qx>mid) return query(o<<1|1,mid+1,r);
	node A=query(o<<1,l,mid),B=query(o<<1|1,mid+1,r),res;
	if(A.mn>=B.mn) res.mn=B.mn,res.id=B.id;
	else res.mn=A.mn,res.id=A.id;
	return res;
}

signed main()
{
//	freopen("anoko.in","r",stdin);
//	freopen("anoko.out","w",stdout);
	read(n,Q);
	build(1,1,n-1);
	For(i,1,n){
		read(a[i]);
		if(a[i]<i) upx=a[i],upy=i-1,upz=1,update(1,1,n-1);
	}
	while(Q--){
		int op;read(op);
		if(op==1){
			int x,v;read(x,v);
			if(a[x]<x&&v<x){
				if(a[x]<v) upx=a[x],upy=v-1,upz=-1,update(1,1,n-1);
				else if(a[x]>v) upx=v,upy=a[x]-1,upz=1,update(1,1,n-1);
				a[x]=v;
			}else{
				if(a[x]<x) upx=a[x],upy=x-1,upz=-1,update(1,1,n-1);
				a[x]=v;
				if(a[x]<x) upx=a[x],upy=x-1,upz=1,update(1,1,n-1);	
			}
		}else{
			int x;read(x);qx=1,qy=x-1;
			if(x==1){ printf("1\n"); continue; }
			node res=query(1,1,n-1);
			if(res.mn>0) printf("1\n");
			else printf("%d\n",res.id+1);
		}
	}
	return 0;
}

源文件, 语言: C++14

详细

Subtask #1:

score: 20

Accepted

Test #1:

score: 20

Accepted

time: 1ms

memory: 5916kb

input:

7 7
7 3 2 7 3 5 3
1 3 4
2 4
1 2 6
2 2
2 5
1 5 3
2 3

output:

result:

ok 4 lines

Test #2:

score: 20

Accepted

time: 1ms

memory: 5900kb

input:

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

output:

result:

ok 7 lines

Test #3:

score: 20

Accepted

time: 1ms

memory: 5860kb

input:

97 97
53 40 75 42 3 49 25 73 36 21 85 8 95 96 91 82 43 32 9 61 14 27 28 39 6 74 6 17 74 48 79 52 35 6 13 44 64 82 5 76 7 2 75 93 20 11 66 76 14 25 4 54 53 11 76 27 26 80 19 17 64 51 96 85 45 55 24 57 56 58 39 75 84 96 69 5 86 93 75 45 60 30 78 38 63 8 26 73 83 87 78 54 28 61 10 70 16
1 14 5
2 24
1 4...

output:

result:

ok 50 lines

Test #4:

score: 20

Accepted

time: 1ms

memory: 5968kb

input:

97 97
34 17 72 6 23 72 75 87 45 97 3 3 34 93 9 63 66 11 50 57 48 21 57 45 96 30 52 47 92 9 71 12 29 20 8 61 88 79 22 50 92 82 24 33 21 59 13 58 93 71 76 10 48 17 70 29 41 88 77 92 38 95 56 11 37 68 25 16 17 55 26 9 5 55 12 96 88 30 51 23 3 46 39 12 78 90 4 33 83 50 81 91 3 13 61 9 15
2 97
1 72 93
2 ...

output:

result:

ok 48 lines

Subtask #2:

score: 20

Accepted

Test #5:

score: 20

Accepted

time: 34ms

memory: 12072kb

input:

100000 100000
100000 1 1 2 4 1 5 4 5 10 6 11 9 9 11 11 15 17 14 16 19 19 19 23 20 21 26 25 26 29 28 27 29 30 32 33 32 36 36 35 39 40 41 41 43 45 44 43 44 117 46 51 48 50 50 52 55 53 54 42 59 61 61 63 94 64 65 64 64 66 68 69 70 69 87 72 72 77 78 75 76 78 78 79 80 84 84 83 84 142 87 87 90 92 80 91 93 ...

output:

result:

ok 100000 lines

Test #6:

score: 20

Accepted

time: 35ms

memory: 9408kb

input:

100000 100000
100000 100000 100000 100000 5 2 6 5 8 10 7 7 9 11 10 11 15 16 18 68 20 17 21 19 123 25 26 25 26 26 27 28 32 31 34 35 34 35 36 38 37 39 39 39 30 41 42 47 46 48 50 51 48 51 53 51 52 55 54 56 59 61 62 63 69 65 62 66 67 168 70 71 68 70 73 73 72 75 74 79 76 78 78 81 76 84 83 84 86 97 87 87 ...

output:

result:

ok 100000 lines

Test #7:

score: 20

Accepted

time: 35ms

memory: 10324kb

input:

100000 100000
100000 100000 100000 1 3 3 4 5 7 10 9 7 9 11 13 12 16 17 18 18 16 17 20 23 41 23 22 23 27 25 28 27 28 32 19 31 35 35 38 51 39 40 40 42 41 41 45 47 47 39 49 51 51 50 47 52 54 56 55 57 56 61 61 62 60 65 66 67 66 106 69 67 70 71 72 74 76 76 76 76 77 77 78 82 80 85 84 83 84 87 89 88 88 93 ...

output:

result:

ok 100000 lines

Test #8:

score: 20

Accepted

time: 41ms

memory: 9316kb

input:

100000 100000
100000 100000 100000 100000 100000 100000 100000 100000 4 100000 100000 100000 8 1 7 100000 12 100000 100000 100000 100000 2 7 12 100000 100000 100000 100000 24 100000 100000 2 100000 34 17 16 1 1 6 37 9 1 26 7 20 6 40 27 8 17 44 5 33 52 45 37 8 52 43 44 30 30 61 27 46 49 34 40 29 28 2...

output:

result:

ok 100000 lines

Test #9:

score: 20

Accepted

time: 23ms

memory: 10596kb

input:

100000 100000
8751 2011 12672 8150 8133 2290 16185 17801 17513 22749 18754 541 31934 1466 21018 30487 17406 15125 391 13136 5501 18415 24356 17256 28496 13606 7333 20048 25868 27702 28662 17824 17026 28114 32443 8813 15650 6043 22441 13593 14326 31713 32338 803 5452 18174 1107 13754 6336 13939 13498...

output:

result:

ok 100000 lines

Test #10:

score: 20

Accepted

time: 27ms

memory: 10548kb

input:

100000 100000
28342 23764 69 16293 8618 19424 30189 12094 8726 31553 11543 9511 8431 20726 20964 27876 27913 24197 13961 18478 5930 10577 24601 24133 26444 17137 25078 31993 8117 12704 2871 10664 4952 10609 25358 172 2293 5120 29969 26359 28610 26872 28007 2463 25689 22401 1668 12073 1379 15691 1732...

output:

result:

ok 100000 lines

Test #11:

score: 20

Accepted

time: 23ms

memory: 9340kb

input:

100000 100000
9 9 4 4 9 15 11 16 16 19 11 12 18 16 18 21 22 19 28 23 26 29 28 27 30 26 32 30 37 30 38 40 41 42 44 42 39 40 47 43 43 45 46 44 49 53 47 52 51 57 55 54 56 62 57 57 58 65 66 69 64 65 67 66 71 70 67 74 75 76 77 75 80 83 77 78 82 81 88 86 87 88 86 86 89 88 93 89 93 99 92 93 100 98 104 100 ...

output:

result:

ok 100000 lines

Test #12:

score: 20

Accepted

time: 28ms

memory: 9264kb

input:

100000 100000
10 8 4 13 6 15 13 9 10 13 11 13 15 14 20 18 24 21 26 29 27 24 28 29 25 30 27 31 34 36 33 37 42 42 40 39 39 43 46 47 50 42 51 51 53 52 50 51 53 53 56 56 61 54 60 62 62 64 61 65 67 63 71 73 73 75 67 76 75 74 74 75 77 75 78 80 86 82 82 80 82 84 83 88 86 90 94 95 98 98 98 101 96 94 101 101...

output:

result:

ok 100000 lines

Test #13:

score: 20

Accepted

time: 39ms

memory: 10820kb

input:

100000 100000
100000 100000 100000 100000 46 4 4 6 6 9 7 10 12 12 13 11 15 15 15 18 17 18 19 23 20 23 26 26 25 31 29 29 32 29 31 33 32 35 37 67 39 39 41 41 44 41 46 43 46 47 50 49 52 49 52 53 54 56 54 58 57 58 62 63 64 61 65 63 64 66 70 70 72 71 71 71 75 75 77 78 79 77 78 82 81 85 84 85 88 87 89 87 ...

output:

result:

ok 100000 lines

Subtask #3:

score: 60

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #14:

score: 60

Accepted

time: 40ms

memory: 9320kb

input:

100000 100000
100000 100000 1 100000 3 2 4 4 5 5 10 11 11 10 13 11 13 15 14 16 19 17 20 23 22 22 24 27 24 29 27 30 30 32 34 32 32 33 34 37 36 38 39 39 44 43 46 46 45 47 50 49 49 51 50 52 55 54 56 57 60 59 59 61 64 65 63 66 67 68 70 71 72 70 74 74 73 76 74 76 79 81 82 82 80 82 83 86 84 85 87 89 91 93...

output:

result:

ok 87500 lines

Test #15:

score: 60

Accepted

time: 39ms

memory: 10304kb

input:

100000 100000
100000 1 2 100000 2 5 6 6 4 7 6 9 11 11 11 11 16 15 15 16 19 18 20 19 23 24 26 27 27 29 29 31 29 32 34 34 33 37 34 38 38 39 40 42 41 41 43 47 47 49 47 47 51 53 50 53 56 54 58 57 59 61 61 59 60 61 64 65 66 68 66 70 70 73 72 74 72 74 74 75 79 77 81 81 82 83 83 84 87 86 87 88 92 91 90 93 ...

output:

result:

ok 87500 lines

Test #16:

score: 60

Accepted

time: 39ms

memory: 10672kb

input:

100000 100000
100000 1 100000 1 1 2 4 5 7 9 6 10 12 9 12 12 14 16 15 19 20 20 18 19 21 23 24 23 28 26 26 31 30 30 33 31 34 36 35 37 39 39 38 43 44 41 46 45 44 45 50 49 52 52 50 54 55 57 55 55 57 59 60 63 61 64 64 64 65 65 67 67 69 72 70 73 75 73 77 79 78 80 80 81 84 85 84 84 85 89 89 90 89 92 94 92 ...

output:

result:

ok 87500 lines

Test #17:

score: 60

Accepted

time: 35ms

memory: 10272kb

input:

100000 100000
100000 100000 100000 100000 3 2 3 7 4 6 9 9 12 12 11 12 15 15 16 19 19 21 18 20 20 21 23 24 24 25 26 27 30 33 31 31 34 36 37 35 36 39 41 42 43 42 45 45 48 45 47 49 49 52 54 54 56 57 55 57 59 61 58 61 64 65 63 63 64 69 68 70 68 71 73 71 72 76 75 77 77 79 79 81 81 85 86 85 87 85 88 87 92...

output:

result:

ok 87500 lines

Test #18:

score: 60

Accepted

time: 39ms

memory: 9428kb

input:

100000 100000
100000 100000 100000 1 100000 2 6 5 4 8 8 9 9 10 14 12 15 16 17 16 16 20 18 23 23 25 25 23 26 29 26 28 31 32 30 33 35 36 38 39 39 40 40 41 42 42 44 46 47 49 46 48 49 51 52 55 55 54 56 55 59 60 59 62 61 62 65 64 64 65 67 67 71 70 72 75 73 77 76 79 80 77 81 80 82 83 85 86 84 85 87 89 88 ...

output:

result:

ok 87500 lines

Test #19:

score: 60

Accepted

time: 35ms

memory: 10764kb

input:

100000 100000
100000 100000 100000 100000 100000 3 4 7 7 6 8 10 10 11 10 12 14 14 16 17 19 17 20 19 24 21 26 25 25 25 28 29 31 29 31 33 34 35 34 35 36 39 42 40 44 44 43 45 47 49 50 47 49 51 50 53 55 55 56 59 57 61 62 61 60 65 66 67 66 66 70 69 71 73 72 73 73 74 77 79 80 80 81 79 80 84 82 87 85 86 86...

output:

result:

ok 87500 lines

Test #20:

score: 60

Accepted

time: 39ms

memory: 10452kb

input:

100000 100000
100000 100000 2 100000 100000 2 5 5 6 8 8 8 9 11 14 13 16 16 18 17 16 19 19 23 23 23 25 23 25 28 26 28 30 33 32 33 35 37 35 36 40 37 38 40 43 44 42 44 46 49 46 51 50 53 51 55 54 53 58 56 60 60 61 60 61 61 63 63 65 65 67 71 68 71 70 74 74 77 77 77 79 81 79 81 81 81 82 87 87 87 89 90 92 ...

output:

result:

ok 87500 lines

Test #21:

score: 60

Accepted

time: 36ms

memory: 10320kb

input:

100000 100000
100000 100000 2 2 1 3 2 3 4 6 6 10 12 9 14 11 15 17 14 19 19 18 20 21 22 25 25 23 25 27 28 28 32 30 30 35 36 35 38 39 38 41 39 43 44 45 43 45 45 45 47 51 50 50 51 52 56 53 58 55 59 58 58 62 60 65 64 67 64 66 70 67 72 69 71 75 73 73 77 79 76 81 78 80 84 81 84 87 86 85 87 88 89 91 90 91 ...

output:

result:

ok 87500 lines

Test #22:

score: 60

Accepted

time: 40ms

memory: 9192kb

input:

100000 100000
100000 100000 1 100000 1 2 4 4 7 8 7 10 8 10 12 15 16 16 16 16 18 21 18 20 24 21 24 23 24 27 30 31 32 33 34 33 32 35 37 35 36 37 41 43 44 43 45 47 47 48 49 49 49 50 51 55 56 54 54 55 59 58 59 60 63 64 65 63 65 68 66 71 70 72 74 71 74 77 75 77 79 78 78 83 80 84 86 85 87 87 88 90 92 91 9...

output:

result:

ok 87500 lines

Test #23:

score: 60

Accepted

time: 39ms

memory: 12064kb

input:

100000 100000
100000 100000 100000 100000 2 1 5 5 8 5 6 7 12 10 12 12 12 15 18 17 16 21 18 22 24 24 22 23 26 25 27 30 31 31 31 34 34 34 38 35 38 38 38 42 42 44 45 44 48 47 46 49 52 53 51 53 54 55 54 57 58 57 59 63 62 62 62 67 66 65 70 70 69 69 72 71 76 74 76 75 78 79 78 79 83 84 83 84 88 88 88 87 88...

output:

result:

ok 87500 lines

Test #24:

score: 60

Accepted

time: 40ms

memory: 9456kb

input:

100000 100000
100000 100000 2 2 4 3 5 3 6 5 10 10 10 11 13 15 14 16 14 16 19 17 22 19 22 21 26 23 24 27 26 27 32 31 30 32 36 33 37 35 39 39 41 42 43 41 42 46 47 49 48 51 48 49 54 55 53 53 54 59 59 59 60 63 60 63 66 64 66 67 67 71 72 70 73 73 75 73 75 77 78 80 81 83 81 85 86 85 86 87 89 89 89 93 92 9...

output:

result:

ok 87500 lines

Test #25:

score: 60

Accepted

time: 30ms

memory: 9584kb

input:

100000 100000
24069 20014 13851 1754 25291 13968 15017 2453 21591 8626 4224 9025 29885 20721 29935 8598 17570 22401 15407 28090 25257 29598 16205 10311 30292 27224 20531 20611 13528 32350 16734 1476 27656 29090 30584 18598 7288 5890 6398 24476 12570 30332 15130 14031 14532 31634 12121 25559 13158 15...

output:

result:

ok 50073 lines

Test #26:

score: 60

Accepted

time: 31ms

memory: 10416kb

input:

100000 100000
29421 5682 25700 17382 16312 14043 19565 28779 11969 11364 11053 8494 10984 22074 10901 10780 16057 17463 4040 17863 6905 16771 28338 9178 6334 9423 1841 21379 19376 5339 100000 21883 11888 23414 3241 19531 22204 22055 11705 11633 14885 28187 207 100000 2516 12540 4546 7297 3656 21181 ...

output:

result:

ok 50040 lines

Test #27:

score: 60

Accepted

time: 15ms

memory: 10176kb

input:

100000 100000
6708 6638 7981 32141 18282 1364 4841 25562 11169 3273 21848 14872 17231 5202 6536 24190 7612 19460 23340 25526 15872 5086 26807 23661 19216 12467 14870 30856 4323 20661 6873 29050 20426 24374 8468 18030 24235 10858 30572 18687 6480 22266 29733 31279 9001 9402 768 13754 30219 763 23707 ...

output:

result:

ok 50047 lines

Test #28:

score: 60

Accepted

time: 35ms

memory: 10900kb

input:

100000 100000
100000 100000 100000 3 4 3 6 6 4 7 6 11 9 9 13 15 16 16 16 16 18 19 18 23 23 24 26 24 25 26 26 31 32 29 33 32 36 36 37 39 39 37 41 39 40 45 43 46 44 49 48 49 49 50 52 52 52 57 58 56 59 58 60 60 61 65 64 65 65 69 66 71 71 69 73 72 75 77 76 79 80 80 80 79 83 83 82 85 85 88 90 88 89 89 94...

output:

result:

ok 87500 lines

Test #29:

score: 60

Accepted

time: 23ms

memory: 9784kb

input:

100000 100000
30755 22792 31994 992 7041 8027 2363 14294 19437 18821 16432 5775 17783 22256 1352 21105 1824 15724 2092 26558 18525 5288 17032 3871 236 20238 1776 16488 32225 1437 7920 17454 2336 21040 31372 22447 8107 14648 27946 24069 14228 9619 32125 9039 5998 29020 17235 12053 15418 466 22127 995...

output:

result:

ok 50065 lines

Test #30:

score: 60

Accepted

time: 15ms

memory: 11888kb

input:

100000 100000
26982 23976 23911 19732 8092 18961 16165 6371 4268 8321 12082 8300 31003 12611 15269 26349 32521 9534 10868 32480 28923 12022 15969 1063 5099 20095 3655 10008 628 8954 27670 18051 6888 19754 23041 6662 32146 25332 4646 28029 7117 28757 7363 27337 22036 2859 30322 29656 10992 29982 1808...

output:

result:

ok 50041 lines

Test #31:

score: 60

Accepted

time: 27ms

memory: 9648kb

input:

100000 100000
1 2 4 6 5 8 2 8 13 14 9 16 14 16 17 15 19 15 20 21 24 18 25 28 23 27 25 24 32 28 26 29 31 34 33 36 34 33 36 35 40 37 43 40 47 43 49 53 52 54 54 48 57 53 57 60 60 57 55 57 61 66 63 63 64 68 65 72 64 68 73 67 68 76 72 80 78 77 74 80 84 77 79 84 88 84 84 84 90 85 93 89 94 98 93 96 94 99 9...

output:

result:

ok 90909 lines

Test #32:

score: 60

Accepted

time: 35ms

memory: 8996kb

input:

100000 100000
1 2 3 9 6 12 13 27 9 10 7 3 18 13 15 31 6 26 29 18 35 32 35 39 23 44 44 39 39 37 38 38 36 49 24 20 22 46 43 42 33 38 60 55 35 35 27 49 31 34 51 70 38 70 64 52 37 39 51 75 72 67 73 46 80 64 76 78 70 71 57 82 69 94 66 76 57 89 79 71 85 98 95 88 74 83 90 102 70 88 101 96 110 106 79 116 97...

output:

result:

ok 90909 lines

Test #33:

score: 60

Accepted

time: 34ms

memory: 9548kb

input:

100000 100000
1 2 3 4 5 9 61 8 79 102 16 12 48 24 106 16 17 18 8 51 11 22 68 24 25 26 27 28 23 30 48 56 35 81 35 36 37 107 117 116 63 104 43 44 45 46 47 66 49 40 51 52 74 142 10 56 44 58 59 150 51 129 84 90 132 155 123 132 17 14 29 133 116 4 75 137 73 78 13 106 96 82 81 100 25 10 168 17 99 70 138 11...

output:

result:

ok 90909 lines