QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #456212 | #964. Excluded Min | 541forever | TL | 2ms | 10112kb | C++20 | 3.8kb | 2024-06-27 14:10:48 | 2024-06-27 14:10:49 |
Judging History
answer
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
struct node
{
int l,r,id;
}q[500001];
int qans[500001];
int num[2000001];
int tag[2000001];
int a[500001];
int n,m,sq;
inline void T(int p,int y)
{
tag[p]+=y,num[p]+=y;
}
inline void push_down(int p)
{
T(p*2,tag[p]);
T(p*2|1,tag[p]);
tag[p]=0;
}
inline void push_up(int p)
{
num[p]=max(num[p*2],num[p*2|1]);
}
void build(int p,int pl,int pr)
{
if(pl==pr)
{
num[p]=-pl;
return ;
}
int mid=(pl+pr)>>1;
build(p*2,pl,mid);
build(p*2|1,mid+1,pr);
push_up(p);
}
void add(int p,int pl,int pr,int l,int r,int y)
{
if(l<=pl&&pr<=r){ T(p,y);return ;}
int mid=(pl+pr)>>1;push_down(p);
if(l<=mid) add(p*2,pl,mid,l,r,y);
if(mid<r) add(p*2|1,mid+1,pr,l,r,y);
push_up(p);
}
int get(int p,int pl,int pr)
{
if(pl==pr) return pl;
int mid=(pl+pr)>>1;push_down(p);
if(num[p*2|1]>=0) return get(p*2|1,mid+1,pr);
return get(p*2,pl,mid);
}
inline void add(int x,int y)
{
if(x>n) return ;
add(1,0,n,x,n,y);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read()+1;
for(;(sq+1)*(sq+1)<=n;sq++);
for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
build(1,0,n);
sort(q+1,q+m+1,[](node a,node b)
{
if(a.l/sq!=b.l/sq) return a.l<b.l;
return a.r<b.r;
});
int l=1,r=0;
for(int i=1;i<=m;i++)
{
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);
while(l<q[i].l) add(a[l++],-1);
qans[q[i].id]=get(1,0,n);
}
for(int i=1;i<=m;i++) printf("%d\n",qans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9988kb
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: 1ms
memory: 9968kb
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: 1ms
memory: 9932kb
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: 1ms
memory: 10112kb
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: 1ms
memory: 10104kb
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: 0
Accepted
time: 0ms
memory: 10048kb
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 1 18 1 5 5 1 1 22 11 0 15 0 59 5 56 1 80 0 1 1 21 0 61 22 11 0 3 8 15 40 1 8 81 71 20 2 0 60 0 60 31 0 59 0 0 0 28 0 21 1 7 5 0 31 0 76 28 0 0 27 1 23 0 1 27 1 0 0 1 0 5 63 52 2 43 73 1 86 0 61 0 27 2 30 5 31 1 0 14 59 27 1 1 67 63
result:
ok 100 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 10112kb
input:
100 100 6 1 1 5 13 11 35 5 3 2 0 4 0 9 1 2 3 3 19 1 7 9 7 11 7 8 10 18 28 17 31 2 4 8 2 3 3 2 22 4 9 4 7 2 9 15 8 2 3 19 5 24 3 10 11 5 9 20 8 4 11 10 18 9 13 34 5 34 2 9 24 6 21 16 6 12 26 2 2 2 6 11 2 14 3 8 2 12 2 19 8 3 18 23 5 21 23 8 4 0 44 67 25 74 24 79 59 73 4 81 42 66 48 55 15 38 35 63 16 ...
output:
22 50 56 0 78 23 0 22 29 24 38 37 17 57 0 6 0 58 52 4 64 44 0 37 75 75 34 89 0 4 0 12 39 0 0 69 53 14 38 13 36 30 0 7 46 83 28 6 44 22 40 50 24 26 36 49 0 0 6 49 27 78 0 37 11 49 16 50 25 30 37 58 64 28 62 36 0 52 0 95 34 4 50 17 0 27 44 0 0 21 44 66 69 0 39 25 0 2 63 0
result:
ok 100 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 9984kb
input:
100 100 0 1 0 1 0 1 1 1 0 2 1 1 2 0 1 1 0 3 0 0 0 0 0 0 0 0 1 2 2 0 0 0 0 1 0 0 1 2 0 0 1 0 0 3 0 1 0 0 3 0 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 2 0 0 0 4 0 1 1 0 1 0 2 2 0 0 1 41 53 31 36 78 99 60 86 1 67 3 92 89 92 60 70 42 56 42 46 39 84 40 66 9 27 75 78 33 94 17 53...
output:
13 6 22 27 67 90 3 11 15 5 46 27 19 4 62 37 84 35 53 4 47 95 55 63 24 39 22 51 67 21 55 36 24 16 33 74 4 16 63 81 41 14 3 54 6 40 36 33 29 32 14 60 13 17 73 44 34 2 14 79 59 13 75 72 31 10 22 57 23 37 74 2 6 6 38 5 4 62 66 22 33 0 23 21 12 54 75 6 8 16 37 36 3 53 63 18 67 60 31 19
result:
ok 100 numbers
Test #9:
score: -100
Time Limit Exceeded
input:
300000 300000 216504 101790 177261 84423 215788 67188 170620 125383 222808 149722 190483 152974 27524 172557 109218 201761 138030 177265 270417 244027 29296 13565 108388 270622 75102 137755 134081 21988 249714 268911 178911 39288 197287 232628 152784 226739 40134 213404 230781 181323 235763 55745 44...