QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #415536 | #964. Excluded Min | Naganohara_Yoimiya | WA | 3ms | 30200kb | C++14 | 5.4kb | 2024-05-20 23:00:45 | 2024-05-20 23:00:45 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define mk make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}
const int N=5e5+5;
int n,m,ans[N],a[N];
struct qry{int l,r,id;}qr[N];
vector<int>pos[N];
struct sgt1{
int d[N<<2];
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
void pushup(int p){d[p]=max(d[ls(p)],d[rs(p)]);}
void build(int l,int r,int p){
if(l==r)return d[p]=qr[l].r,void();
int mid=(l+r)>>1;build(l,mid,ls(p)),build(mid+1,r,rs(p)),pushup(p);
}
int qval(int l,int r,int v,int ql,int qr,int p){
// cout<<"qval l,r = "<<l<<" "<<r<<" v = "<<v<<" ql,qr = "<<ql<<" "<<qr<<" p = "<<p<<" mx = "<<d[p]<<endl;
if(d[p]<=v||ql>r||qr<l||l>r)return -1;
if(ql==qr)return ql;
int mid=(ql+qr)>>1;
int ret=qval(l,r,v,ql,mid,ls(p));
if(ret!=-1)return ret;
return qval(l,r,v,mid+1,qr,rs(p));
}
void modify(int x,int v,int ql,int qr,int p){
// cout<<"modify x,v = "<<x<<" "<<v<<" ql,qr = "<<ql<<" "<<qr<<endl;
if(ql==qr)return d[p]=v,void();
int mid=(ql+qr)>>1;
if(x<=mid)modify(x,v,ql,mid,ls(p));
if(x>mid)modify(x,v,mid+1,qr,rs(p));
pushup(p);
// cout<<" -> ql,qr = "<<ql<<" "<<qr<<" p = "<<p<<" d = "<<d[p]<<endl;
}
#undef ls
#undef rs
}T1;
struct BIT{
int c[N];
int lowbit(int x){return x&(-x);}
void add(int x,int v){for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;}
int qsum(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=c[i];return res;}
int sum(int l,int r){return qsum(r)-qsum(l-1);}
}B;
set<int>ids;
int now;
vector<int>adds;
const int INF=1e9;
void del(int p){
// cout<<"del p = "<<p<<" now = "<<now<<endl;
T1.modify(p,-INF,1,m,1);
auto it=ids.find(p);
int q=0;if(it!=ids.begin())q=(*prev(it));ids.erase(it);
ans[qr[p].id]=now;
// cout<<" q = "<<q<<endl;
int pre=qr[q].r;
q=T1.qval(q+1,m,pre,1,m,1);
// cout<<" -> q = "<<q<<endl;
// exit(0);
while(q!=-1&&ids.find(q)==ids.end()){
// cout<<" -> q = "<<q<<endl;
if(B.sum(qr[q].l,qr[q].r)>=now){
ans[qr[q].id]=now,T1.modify(q,-INF,1,m,1);
}
else ids.insert(q),pre=qr[q].r,adds.emplace_back(q);
q=T1.qval(q+1,m,pre,1,m,1);
// cout<<" -> q = "<<q<<endl;
}
// cout<<" -> ids = ";for(int x:ids)cout<<x<<" ";puts("");
}
bool In[N];
struct Node{int sl,sr,tl,tr,mx;};
struct sgt2{
Node d[N<<2];int lz[N<<2];
void app(int p,int f){lz[p]+=f,d[p].mx+=f;}
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
void pushdown(int p){if(lz[p]!=0)app(ls(p),lz[p]),app(rs(p),lz[p]),lz[p]=0;}
void pushup(int p){
if(d[ls(p)].sr==0)d[p]=d[rs(p)];
else if(d[rs(p)].sr==0)d[p]=d[ls(p)];
else{
d[p].mx=max(d[ls(p)].mx,d[rs(p)].mx);
d[p].sl=d[ls(p)].sl,d[p].sr=d[ls(p)].sr;
d[p].tl=d[rs(p)].tl,d[p].tr=d[rs(p)].tr;
}
}
void build(int l,int r,int p){
lz[p]=0;
if(l==r){
if(In[l]){
auto [L,R,id]=qr[l];
d[p].sl=d[p].tl=L,d[p].sr=d[p].tr=R;
d[p].mx=R-L+1-n;
}
else{
d[p].sl=d[p].tl=n+1,d[p].sr=d[p].tr=0;
d[p].mx=-INF;
}
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls(p)),build(mid+1,r,rs(p)),pushup(p);
}
void add_all(int v){app(1,v);}
void add(int x,int v,int p){
// cout<<"add x,v = "<<x<<" "<<v<<" p = "<<p<<endl;
if(d[p].sl>x||d[p].tr<x)return ;
// puts("In");
if(d[p].sr>=x&&d[p].tl<=x)return app(p,v);
pushdown(p);
add(x,v,ls(p)),add(x,v,rs(p)),pushup(p);
}
void act(int x,int l,int r,int p){
// cout<<"act x = "<<x<<" l,r = "<<l<<" "<<r<<" p = "<<p<<" now mx = "<<d[p].mx<<endl;
if(l==r){
auto [L,R,id]=qr[x];
// cout<<"L,R = "<<L<<" "<<R<<" sum = "<<B.sum(L,R)<<endl;
d[p].tl=d[p].sl=L,d[p].tr=d[p].sr=R;
d[p].mx=B.sum(L,R)-now;
return ;
}
int mid=(l+r)>>1;pushdown(p);
if(x<=mid)act(x,l,mid,ls(p));
else act(x,mid+1,r,rs(p));
pushup(p);
// cout<<" -> l,r = "<<l<<" "<<r<<" mx = "<<d[p].mx<<" LI = ["<<d[p].sl<<","<<d[p].sr<<"] RI = ["<<d[p].tl<<","<<d[p].tr<<"]"<<endl;
}
void chk(int ql,int qr,int p){
// cout<<"chk ql,qr = "<<ql<<" "<<qr<<" p = "<<p<<" mx = "<<d[p].mx<<endl;
if(d[p].mx<0)return ;
if(ql==qr){
del(ql);
d[p].mx=-INF,d[p].sl=d[p].tl=n+1,d[p].sr=d[p].tr=0;
return ;
}
int mid=(ql+qr)>>1;pushdown(p);
chk(ql,mid,ls(p)),chk(mid+1,qr,rs(p)),pushup(p);
}
#undef ls
#undef rs
}T2;
signed main(void){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read(),pos[a[i]].emplace_back(i);
for(int i=1;i<=m;i++)qr[i].l=read(),qr[i].r=read(),qr[i].id=i;
// puts("ok");
sort(qr+1,qr+m+1,[&](qry A,qry B){
if(A.l==B.l)return A.r<B.r;
return A.l<B.l;
});
// cout<<"qr = ";for(int i=1;i<=m;i++)cout<<"["<<qr[i].l<<","<<qr[i].r<<"] ";puts("");
int cur_mx=0;
for(int i=1;i<=m;i++)if(qr[i].r>cur_mx){
ids.insert(i),In[i]=true,cur_mx=qr[i].r;
}
for(int i=1;i<=n;i++)B.add(i,1);
T2.build(1,m,1),T1.build(1,m,1);
// puts("ok");
now=n;
for(int i=n;i>=1;i--){
// cout<<"===== i = "<<i<<" =====\n";
T2.chk(1,m,1);
for(int p:adds)T2.act(p,1,m,1);vector<int>().swap(adds);
for(int p:pos[i-1])T2.add(p,-1,1);
for(int p:pos[i-1])B.add(p,-1);
T2.add_all(1);
now--;
}
for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 26136kb
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: 3ms
memory: 28204kb
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: 0ms
memory: 26164kb
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: 30200kb
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: -100
Wrong Answer
time: 0ms
memory: 28096kb
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:
69 1 1 1 1 1 0 0 0 2 2 0 1 0 0 1 0 2 0 0 2 0 0 0 1 0 0 28 1 2 0 0 0 0 2 1 0 2 0 0 2 2 2 0 0 0 1 0 0 1 1 46 0 0 2 1 1 0 2 2 2 0 49 0 0 1 0 1 0 0 28 0 1 0 2 1 29 0 1 1 28 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 2 0 0
result:
wrong answer 1st numbers differ - expected: '68', found: '69'