QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #763719 | #964. Excluded Min | AlicX | RE | 2ms | 16224kb | C++14 | 3.1kb | 2024-11-19 21:46:30 | 2024-11-19 21:46:30 |
Judging History
answer
#include<bits/stdc++.h>
#define il inline
#define debug() puts("-----")
using namespace std;
il int read(){
int x=0,f=1; 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();
return x*f;
}
const int N=5e5+10,V=720;
int n,m;
int len;
int a[N];
int id[N];
int up,Len;
int ans[N];
int L[N],R[N];
struct Que{
int l,r,id;
il bool operator<(const Que& Liny)const{
if(l/len!=Liny.l/len) return l<Liny.l;
return (l&len)?r<Liny.r:r>Liny.r;
}
}q[N];
struct Node{
int l,r;
int w,tag;
}tr[V][V<<2]; int pid;
int Tr[N];
#define low(x) x&-x
il void Add(int x,int k){
for(int i=x;i<=id[up];i+=low(i)) Tr[i]+=k;
}
il int qry(int x){
int res=0;
for(int i=x;i;i-=low(i)) res+=Tr[i];
return res;
}
il void pushdown(int u){
if(!tr[pid][u].tag) return ;
tr[pid][u<<1].w+=tr[pid][u].tag,tr[pid][u<<1|1].w+=tr[pid][u].tag;
tr[pid][u<<1].tag+=tr[pid][u].tag,tr[pid][u<<1|1].tag+=tr[pid][u].tag;
tr[pid][u].tag=0;
}
il void build(int u,int l,int r){
tr[pid][u]={l,r};
if(l==r){
tr[pid][u].w=L[pid]+l-2;
return ;
} int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
tr[pid][u].w=min(tr[pid][u<<1].w,tr[pid][u<<1|1].w);
}
il void modify(int u,int l,int r,int tag){
if(l<=tr[pid][u].l&&tr[pid][u].r<=r){
tr[pid][u].w+=tag;
tr[pid][u].tag+=tag;
return ;
} pushdown(u);
int mid=tr[pid][u].l+tr[pid][u].r>>1;
if(l<=mid) modify(u<<1,l,r,tag);
if(r>mid) modify(u<<1|1,l,r,tag);
tr[pid][u].w=min(tr[pid][u<<1].w,tr[pid][u<<1|1].w);
}
il int query(int u,int l,int r){
if(l<=tr[pid][u].l&&tr[pid][u].r<=r) return tr[pid][u].w;
pushdown(u);
int w=1e9,mid=tr[pid][u].l+tr[pid][u].r>>1;
if(l<=mid) w=query(u<<1,l,r);
if(r>mid) w=min(w,query(u<<1|1,l,r));
return w;
}
il void add(int x,int k){
// cout<<x<<" ded "<<-k<<" ";
if(x!=R[id[x]]) pid=id[x],modify(1,x-L[id[x]]+2,R[id[x]]-L[id[x]]+1,-k);
// cout<<id[x]+1<<endl;
Add(id[x]+1,-k);
}
il int calc(){
for(int i=id[up];i>=1;i--){
pid=i;
int w=query(1,1,R[i]-L[i]+1),tag=qry(i);
// cout<<w<<" "<<tag<<endl;
if(w+tag<=0){
for(int j=R[i];j>=L[i];j--){
// cout<<j<<" "<<query(1,j-L[i]+1,j-L[i]+1)<<endl;
if(query(1,j-L[i]+1,j-L[i]+1)+tag<=0) return j;
} break;
}
} return 0;
}
signed main(){
n=read(),m=read(); len=sqrt(n);
for(int i=1;i<=n;i++) a[i]=read()+1,up=max(up,a[i]);
up=max(up,n); up++,Len=sqrt(up);
for(int i=1;i<=up;i++) id[i]=(i-1)/Len+1;
for(int i=1;i<=id[up];i++){
L[i]=(i-1)*Len+1;
R[i]=min(up,i*Len);
pid=i,build(1,1,R[i]-L[i]+1);
} for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+m+1); int l=1,r=0;
for(int i=1;i<=m;i++){
while(l>q[i].l) add(a[--l],1);
while(r<q[i].r) add(a[++r],1);
while(l<q[i].l) add(a[l++],-1);
while(r>q[i].r) add(a[r--],-1);
ans[q[i].id]=calc();
} for(int i=1;i<=m;i++) printf("%d\n",ans[i]-1);
return 0;
} /*
10 1
3 0 0 0 5 1 1 1 2 1
1 7
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 16224kb
input:
3 3 0 0 2 1 3 2 3 3 3
output:
3 1 0
result:
ok 3 number(s): "3 1 0"
Test #2:
score: 0
Accepted
time: 0ms
memory: 16104kb
input:
3 2 1 2 2 1 2 1 3
output:
0 3
result:
ok 2 number(s): "0 3"
Test #3:
score: 0
Accepted
time: 2ms
memory: 16152kb
input:
10 10 3 0 3 3 9 7 9 6 0 7 3 3 9 9 4 6 1 9 3 4 2 4 7 10 3 7 5 7 2 7
output:
0 1 0 5 0 1 1 0 0 1
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 16144kb
input:
10 10 3 0 0 0 5 1 1 1 2 1 1 2 8 8 5 7 1 7 2 2 1 5 5 6 4 6 3 10 6 8
output:
1 0 2 7 1 4 0 2 8 3
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 2ms
memory: 13968kb
input:
100 100 15 82 7 39 63 55 64 99 71 63 32 99 67 94 3 43 15 75 45 55 53 4 35 36 15 40 82 20 62 43 6 83 27 95 27 45 98 44 35 98 39 7 17 32 76 7 40 16 40 63 13 8 22 27 11 12 61 14 19 45 100 97 90 88 22 59 25 63 4 25 65 16 22 92 84 44 99 66 89 26 93 97 35 97 92 1 32 40 97 97 78 43 7 12 23 53 61 74 33 90 1...
output:
68 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 48 0 0 0 0 0 0 0 0 0 0 0 0 0 28 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 100 numbers
Test #6:
score: -100
Runtime Error
input:
100 100 17 86 33 8 11 27 8 11 13 9 3 43 11 23 26 42 44 12 44 12 15 0 75 51 72 5 49 2 40 57 24 47 39 42 4 5 6 52 3 2 42 19 62 33 24 22 16 69 4 33 44 70 29 11 2 2 58 9 6 10 25 10 33 26 17 3 14 0 48 7 48 51 0 39 54 37 14 9 3 85 18 4 25 9 2 0 39 8 17 13 25 45 10 39 12 18 9 5 66 6 13 89 10 90 42 67 43 52...