QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #497969 | #7367. 群岛 | MSavannah | 0 | 22ms | 10352kb | C++14 | 2.6kb | 2024-07-29 21:06:51 | 2024-07-29 21:06:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define il inline
il int read()
{
int xr=0,F=1;char cr;
while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
while(cr>='0'&&cr<='9') xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
return xr*F;
}
const int N=100010;
int n,m,a[N],opt,x,y;
struct node{int l,r,mn,laz;}tr[N<<2];
struct Tree{
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
void build(int k,int l,int r)
{
tr[k].l=l,tr[k].r=r;
if(l==r){tr[k].mn=0;return ;}
build(ls,l,mid);build(rs,mid+1,r);
pushup(k);
}
void pushup(int k)
{
tr[k].mn=min(tr[ls].mn,tr[rs].mn);
if(tr[ls].mn<tr[rs].mn) tr[k].r=tr[ls].r;
else tr[k].r=tr[rs].r;
}
void pushdown(int k)
{
tr[ls].mn+=tr[k].laz;tr[ls].laz+=tr[k].laz;
tr[rs].mn+=tr[k].laz;tr[rs].laz+=tr[k].laz;
tr[k].laz=0;
}
void add(int k,int l,int r,int ql,int qr,int v)
{
if(ql<=l&&r<=qr){tr[k].mn+=v,tr[k].laz+=v;return ;}
pushdown(k);
if(ql<=mid) add(ls,l,mid,ql,qr,v);
if(qr>mid) add(rs,mid+1,r,ql,qr,v);
pushup(k);
}
/*int query(int k,int l,int r,int ql,int qr)
{
if(ql==l&&r==qr)
{
if(!tr[k].mn) return tr[k].r;
return -1;
}
pushdown(k);int res=0;
if(qr<mid) res=query(ls,l,mid,ql,qr);
else if(ql>=mid) res=query(rs,mid+1,r,ql,qr);
else
{
int p=query(rs,mid+1,r,mid+1,qr);
if(p!=-1) res=p;else p=query(ls,l,mid,ql,mid);
}
pushup(k);
return res;
}*/
int query(int k,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)
{
if(!tr[k].mn) return tr[k].r;
return -1;
}
pushdown(k);int res=0;
if(qr>mid) res=query(rs,mid+1,r,ql,qr);
if(res!=-1) return res;
else res=query(ls,l,mid,ql,qr);
return res;
}
}seg;
int main()
{
n=read(),m=read();
seg.build(1,1,n);
for(int i=1;i<=n;i++)
{
a[i]=read();
if(a[i]>=i) a[i]=i;
seg.add(1,1,n,a[i]+1,i,1);
}
while(m--)
{
opt=read();
if(opt==1)
{
x=read(),y=read();
seg.add(1,1,n,a[x]+1,x,-1);
a[x]=y;
seg.add(1,1,n,a[x]+1,x,1);
}
if(opt==2)
{
x=read();
int k=seg.query(1,1,n,1,x);
if(!k) printf("-1\n");
else printf("%d\n",k);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5768kb
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:
-1 -1 -1 -1
result:
wrong answer 1st lines differ - expected: '3', found: '-1'
Subtask #2:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 22ms
memory: 10352kb
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:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
wrong answer 1st lines differ - expected: '7955', found: '-1'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%