QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #619317 | #6357. 排序 | McIron233 | 100 ✓ | 1130ms | 16408kb | C++14 | 2.1kb | 2024-10-07 13:51:48 | 2024-10-07 13:51:48 |
Judging History
answer
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
struct qwe{int opt,l,r;}q[N];
int n,m,que,a[N];
struct segment_tree{
int val[N],tag[N];
void buildseg(int k,int l,int r,int v){
if(l==r){
val[k]=(a[l]>=v);
tag[k]=0;
return;
}
int mid=l+r>>1;
buildseg(k<<1,l,mid,v);
buildseg(k<<1|1,mid+1,r,v);
val[k]=val[k<<1]+val[k<<1|1];
tag[k]=0;
}
void pushdown(int k,int l,int r){
if(!tag[k])return;
int mid=l+r>>1;
if(tag[k]==1){
val[k<<1]=mid-l+1,val[k<<1|1]=r-mid;
}
else{
val[k<<1]=0,val[k<<1|1]=0;
}
tag[k<<1]=tag[k],tag[k<<1|1]=tag[k];
tag[k]=0;
}
int query(int k,int l,int r,int ql,int qr){
if(ql>r || qr<l)return 0;
if(ql<=l && r<=qr)return val[k];
int mid=l+r>>1;
pushdown(k,l,r);
int sum1=query(k<<1,l,mid,ql,qr);
int sum2=query(k<<1|1,mid+1,r,ql,qr);
return sum1+sum2;
}
int queryp(int k,int l,int r,int qp){
if(l==r && l==qp)return val[k];
int mid=l+r>>1;
pushdown(k,l,r);
if(qp<=mid)return queryp(k<<1,l,mid,qp);
else return queryp(k<<1|1,mid+1,r,qp);
}
void modify(int k,int l,int r,int ql,int qr,int v){
if(r<ql || l>qr)return;
if(ql<=l && r<=qr){
val[k]=(r-l+1)*v;
tag[k]=v?1:-1;
return;
}
pushdown(k,l,r);
int mid=l+r>>1;
modify(k<<1,l,mid,ql,qr,v);
modify(k<<1|1,mid+1,r,ql,qr,v);
val[k]=val[k<<1]+val[k<<1|1];
}
}seg;
bool chk(int v){
seg.buildseg(1,1,n,v);
for(int i=1;i<=m;++i){
int onecnt=seg.query(1,1,n,q[i].l,q[i].r);
if(q[i].opt==0){
seg.modify(1,1,n,q[i].l,q[i].r-onecnt,0);
seg.modify(1,1,n,q[i].r-onecnt+1,q[i].r,1);
}
if(q[i].opt==1){
seg.modify(1,1,n,q[i].l,q[i].l+onecnt-1,1);
seg.modify(1,1,n,q[i].l+onecnt,q[i].r,0);
}
}
return seg.queryp(1,1,n,que);
}
signed main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",a+i);
for(int i=1;i<=m;++i)scanf("%d %d %d",&q[i].opt,&q[i].l,&q[i].r);
scanf("%d",&que);
int _l=1,_r=n,_mid=114514,ans;
while(_l<=_r){
(_mid)=_l+_r>>1;
if(chk(_mid)){
ans=_mid;
_l=_mid+1;
}else _r=_mid-1;
}
printf("%d",ans);
return 0;
}
详细
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 9968kb
input:
100 100 46 2 24 25 18 43 19 38 9 6 7 30 16 33 32 47 22 1 14 5 45 23 50 48 40 3 26 21 20 39 29 34 42 17 11 4 12 31 49 8 28 10 44 36 35 37 13 15 41 27 95 55 76 84 63 70 83 89 94 65 100 54 69 86 53 71 57 77 68 81 58 56 64 51 88 74 79 82 52 61 73 96 92 72 78 97 66 60 87 90 93 98 80 91 99 75 85 67 59 62 ...
output:
62
result:
ok 1 number(s): "62"
Test #2:
score: 10
Accepted
time: 1ms
memory: 10096kb
input:
100 100 3 28 34 50 2 31 11 23 21 5 13 24 20 39 12 8 46 37 49 6 43 19 42 33 17 4 45 40 47 18 15 35 38 44 7 26 30 9 14 32 25 22 29 1 10 16 36 41 48 27 88 66 59 94 95 99 69 81 79 90 60 86 76 61 85 56 54 82 63 80 75 83 64 97 72 71 52 87 100 55 84 78 62 68 77 89 93 92 58 96 73 91 53 67 65 51 57 74 70 98 ...
output:
16
result:
ok 1 number(s): "16"
Test #3:
score: 10
Accepted
time: 1ms
memory: 9964kb
input:
100 100 20 2 1 44 39 15 23 37 25 33 13 14 16 42 26 35 12 32 5 19 11 4 45 24 30 3 27 41 7 10 9 31 48 28 6 21 18 17 8 22 43 29 50 38 36 49 47 40 34 46 55 53 66 72 98 51 71 74 62 54 81 69 91 84 52 65 76 87 94 61 80 99 83 88 63 97 100 75 85 82 92 86 64 67 70 60 56 57 77 58 79 89 90 78 96 68 73 59 93 95 ...
output:
21
result:
ok 1 number(s): "21"
Test #4:
score: 10
Accepted
time: 157ms
memory: 10116kb
input:
8050 22018 1 29 31 10 16 46 42 23 44 15 37 17 26 28 48 18 9 39 12 2 41 38 25 5 33 20 34 35 7 6 8 32 4 40 49 3 21 13 50 45 19 27 14 11 24 36 30 43 47 22 69 84 88 100 72 76 95 65 99 87 77 83 70 73 97 67 58 62 71 86 80 57 82 63 91 90 96 85 52 59 94 64 51 60 56 55 74 93 75 68 79 98 81 61 53 66 54 78 92 ...
output:
1622
result:
ok 1 number(s): "1622"
Test #5:
score: 10
Accepted
time: 126ms
memory: 10108kb
input:
1400 31558 11 16 45 42 41 50 10 47 24 38 13 27 43 46 22 39 23 29 32 33 49 25 21 28 14 4 34 8 17 36 48 6 1 35 12 30 44 19 2 40 5 15 18 7 9 26 3 20 31 37 67 57 94 76 66 88 85 86 54 89 79 80 63 74 75 69 78 96 87 91 97 95 61 73 55 62 64 65 92 93 59 99 52 71 53 70 60 100 84 68 58 77 56 90 83 51 72 82 98 ...
output:
1241
result:
ok 1 number(s): "1241"
Test #6:
score: 10
Accepted
time: 33ms
memory: 10052kb
input:
1650 7019 9 15 16 46 19 44 13 11 50 37 5 7 23 36 42 30 34 1 28 45 38 31 21 40 8 24 43 6 48 14 22 39 47 2 29 27 17 35 4 3 10 41 20 12 25 26 49 33 18 32 70 99 74 89 51 82 97 60 88 63 61 90 52 94 57 75 81 76 85 65 91 86 59 66 72 56 93 96 71 79 73 54 98 64 69 83 68 62 53 78 95 55 100 87 80 67 77 92 58 8...
output:
954
result:
ok 1 number(s): "954"
Test #7:
score: 10
Accepted
time: 156ms
memory: 9976kb
input:
8700 23581 7 42 44 23 38 25 50 37 20 18 21 3 34 19 11 22 12 17 40 4 30 15 39 28 13 27 1 32 31 24 49 45 33 5 26 43 16 14 2 46 48 10 36 29 8 35 41 9 6 47 92 78 88 66 93 61 63 60 98 64 75 82 59 52 97 70 79 56 90 81 94 57 67 80 100 89 55 99 68 95 86 76 91 62 54 53 83 69 85 72 77 84 96 58 65 73 87 74 71 ...
output:
283
result:
ok 1 number(s): "283"
Test #8:
score: 10
Accepted
time: 90ms
memory: 10096kb
input:
9150 13084 9 20 10 44 3 36 1 11 19 23 17 14 27 12 25 2 15 21 26 39 29 22 28 49 16 24 37 7 4 13 50 33 8 31 32 47 42 18 6 5 48 45 46 30 38 41 43 40 35 34 82 51 95 75 73 89 99 63 100 96 61 70 57 93 84 59 87 94 60 85 56 88 81 76 66 64 83 53 71 72 78 67 80 55 74 91 69 68 54 90 98 65 58 86 77 79 92 62 97 ...
output:
973
result:
ok 1 number(s): "973"
Test #9:
score: 10
Accepted
time: 1130ms
memory: 10872kb
input:
100000 100000 9 23 49 19 16 15 1 46 48 11 33 5 21 31 4 43 26 20 13 22 42 10 38 8 34 37 45 7 36 24 6 39 3 18 2 27 44 40 17 50 32 35 29 12 28 25 47 41 30 14 65 87 53 69 86 72 77 63 99 100 75 84 81 95 91 89 80 96 73 52 83 60 66 94 71 59 62 56 92 58 55 68 51 70 90 93 64 74 97 82 88 79 54 76 78 67 98 61 ...
output:
6922
result:
ok 1 number(s): "6922"
Test #10:
score: 10
Accepted
time: 1083ms
memory: 16408kb
input:
100000 100000 21 28 36 2 16 48 19 37 7 5 44 30 22 45 3 15 8 9 20 38 12 50 1 43 25 11 4 14 46 13 42 39 10 49 35 17 26 33 23 27 6 18 34 41 29 47 24 31 32 40 93 69 70 91 61 94 87 58 92 73 86 96 64 84 52 98 77 71 53 55 62 75 56 59 68 67 88 83 78 100 54 95 74 97 65 60 80 85 66 72 79 90 76 82 57 51 99 63 ...
output:
13716
result:
ok 1 number(s): "13716"