QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#819077 | #964. Excluded Min | lgvc | WA | 5ms | 22124kb | C++23 | 4.8kb | 2024-12-18 12:17:52 | 2024-12-18 12:17:52 |
Judging History
answer
#include <bits/stdc++.h>
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
*pp++=ch;
}
inline void pcc(){
fwrite(buf2,1,pp-buf2,stdout);
pp=buf2;
}
inline int read(void){
register int x(0);register char c(getchar());
while(c<'0'||c>'9'){c=getchar();}
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
void write(int x){
static int sta[20];
int top=0;
do{
sta[top++]=x%10,x/=10;
}while(x);
while(top) pc(sta[--top]+48);
}
void we(int x){
write(x);
pc('\n');
}
int N,Q,a[500009],as[500009],v[500009];
std::vector<int> t[500009];
struct n_t{
int l,r,i;
} q[500009];
bool operator<(n_t x,n_t y) {
if(x.l!=y.l) return x.l<y.l;
if(x.r==y.r) return x.i<y.i;
return x.r>y.r;
}
struct p_t{
int a,b;
};
bool operator<(p_t x,p_t y) {
return x.a<y.a;
}
std::set<n_t> ss;
std::set<p_t> ss2;
void rm(int p);
#define ls (n<<1)
#define rs ((n<<1)|1)
#define md ((l+r)>>1)
int laz[2000009],ma[2000009];
void up(int n,int l,int r,int L,int R) {
if(r<L||R<l) return;
if(L<=l&&r<=R) {
laz[n]++;
ma[n]--;
return;
}
up(ls,l,md,L,R);
up(rs,md+1,r,L,R);
ma[n]=std::max(ma[ls],ma[rs])-laz[n];
}
void cl(int n,int l,int r,int v) {
if(l==r) {
as[q[l].i]=v;
rm(l);
return;
}
ma[ls]-=laz[n];
ma[rs]-=laz[n];
laz[ls]+=laz[n];
laz[rs]+=laz[n];
laz[n]=0;
if(ma[ls]>=v) {
cl(ls,l,md,v);
} else {
cl(rs,md+1,r,v);
}
}
void up2(int n,int l,int r,int p,int v) {
if(l==r) {
ma[n]=v;
return;
}
ma[ls]-=laz[n];
ma[rs]-=laz[n];
laz[ls]+=laz[n];
laz[rs]+=laz[n];
laz[n]=0;
if(p<=md) up2(ls,l,md,p,v);
else up2(rs,md+1,r,p,v);
ma[n]=std::max(ma[ls],ma[rs])-laz[n];
}
void er4(int n,int l,int r,int p) {
if(l==r) {
ma[n]=-0x3f3f3f3f;
return;
}
ma[ls]-=laz[n];
ma[rs]-=laz[n];
laz[ls]+=laz[n];
laz[rs]+=laz[n];
laz[n]=0;
if(p<=md) er4(ls,l,md,p);
else er4(rs,md+1,r,p);
ma[n]=std::max(ma[ls],ma[rs])-laz[n];
}
int ma2[2000009];
void er3(int n,int l,int r,int p) {
if(l==r) {
ma2[n]=-0x3f3f3f3f;
return;
}
if(p<=md) er3(ls,l,md,p);
else er3(rs,md+1,r,p);
ma2[n]=std::max(ma2[ls],ma2[rs]);
}
void bd(int n,int l,int r) {
if(l==r) {
ma2[n]=q[l].r;
return;
}
bd(ls,l,md);
bd(rs,md+1,r);
ma2[n]=std::max(ma2[ls],ma2[rs]);
}
int f2(int n,int l,int r,int v) {
if(ma2[n]<v) return r+1;
if(l==r) return l;
int a=f2(ls,l,md,v);
if(a==md+1) a=f2(rs,md+1,r,v);
return a;
}
void is(int p) {
// printf("is %d\n",p);
int l=q[p].l,r=q[p].r;
ss.insert((n_t){l,r,p});
ss2.insert((p_t){r,p});
int va=r-l+1;
for(int i=l;i<=r;i++) if(v[i]) va--;
up2(1,1,Q,p,va);
er3(1,1,Q,p);
}
void rm(int p) {
// printf("rm %d\n",p);
er4(1,1,Q,p);
int l=q[p].l,r=q[p].r;
ss2.erase((p_t){r,p});
auto it=ss.find((n_t){l,r,p});
int id=0;
if(it==ss.begin()) {
id=0;
} else {
it--;
id=(*it).r;
}
//printf("%d\n",id);
ss.erase((n_t){l,r,p});
while(1) {
int pt=f2(1,1,Q,id+1);
if(pt>Q||q[pt].r>r) {
break;
}
is(pt);
id=q[pt].r;
}
}
signed main(void) {
N=read();Q=read();
for(int i=1;i<=N;i++) {
a[i]=read();
t[a[i]].push_back(i);
}
for(int i=1;i<=Q;i++) {
q[i].l=read();
q[i].r=read();
q[i].i=i;
}
std::sort(q+1,q+Q+1);
int maa=0;
memset(ma,-0x3f,sizeof(ma));
bd(1,1,Q);
for(int i=1;i<=Q;i++) {
if(maa<q[i].r) {
is(i);
maa=q[i].r;
}
}
for(int i=500000;i>=1;i--) {
for(int j=0;j<t[i].size();j++) {
int p=t[i][j];
v[p]=1;
int l=0,r=Q,mm;
while(l<r) {
mm=(l+r+1)/2;
if(q[mm].l<=p) l=mm;else r=mm-1;
}
auto it=ss2.lower_bound((p_t){p,0});
int tq;
if(it==ss2.end()) {
tq=Q+1;
} else {
tq=(*it).b;
}
if(tq<=l) {
// printf("%d %d %d\n",p,tq,l);
up(1,1,Q,tq,l);
}
}
while(ma[1]>=i) {
cl(1,1,Q,i);
}
}
for(int i=1;i<=Q;i++) we(as[i]);
pcc();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22012kb
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: 2ms
memory: 22124kb
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: 5ms
memory: 21988kb
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: 21912kb
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: 0ms
memory: 21976kb
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
Wrong Answer
time: 5ms
memory: 22024kb
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...
output:
76 80 0 0 18 0 18 1 5 5 1 1 22 11 0 15 0 59 8 56 1 80 0 1 2 21 0 61 22 11 0 3 8 15 40 1 8 81 71 20 2 2 60 0 60 31 2 59 0 0 0 30 0 21 1 7 4 0 31 0 76 28 0 0 27 2 23 0 1 27 1 0 0 1 0 5 63 52 1 43 73 1 86 0 61 0 27 2 30 11 31 1 0 14 59 27 1 0 67 63
result:
wrong answer 6th numbers differ - expected: '1', found: '0'