QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#33721 | #4219. Insects | Qingyu | WA | 3ms | 9952kb | C++23 | 2.9kb | 2022-06-04 18:22:24 | 2022-06-04 18:22:24 |
Judging History
answer
// xtqqwq
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
int readint(){
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*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,nx,ny,k;
int px[200005],py[200005],g[200005],del[200005],ans[100005];
pii a[100005],b[100005];
pair<pii,int> val[200005];
void add(int x,int y){
for(;x<=m;x+=(x&(-x))) g[x]+=y;
}
int ask(int x){
int ret=0;
for(;x;x-=(x&(-x))) ret+=g[x];
return ret;
}
void solve(int l,int r,vector<pair<pii,int> > &vec,int sum){
// cout<<"######################### solve "<<l<<' '<<r<<' '<<sum<<endl;
// for(auto r:vec) cout<<r.se<<' ';
// cout<<endl;
int mid=(l+r)/2;
k=0;
for(auto r:vec) if(r.se<=mid) val[++k]=r;
sort(val+1,val+k+1,[&](pair<pii,int> x,pair<pii,int> y){return x.fi==y.fi?x.se<y.se:x.fi.fi==y.fi.fi?x.fi.se>y.fi.se:x.fi.fi<y.fi.fi;});
multiset<int> st;
int all=0;
for(int i=1;i<=k;i++){
if(val[i].se){
auto it=st.upper_bound(val[i].fi.se);
if(it!=st.begin()){
it--;
all++;
del[i]=*it;
st.erase(it);
}
else del[i]=0;
}
else st.insert(val[i].fi.se);
}
// cout<<"test "<<mid<<' '<<all<<' '<<ask(l)<<endl;
if(l==r) return (void)(ans[l]=sum+all+ask(l));
int pl=1,rval=0;
vector<int> chn;
vector<pair<pii,int> > lson,rson;
for(int i=k;i>=1;i--){
if(val[i].se){
if(val[i].fi.se>=pl&&pl>=del[i]) pl=val[i].fi.se+1;
}
if(val[i].fi.se<pl){
lson.pb(val[i]),rval+=val[i].se==0;
}
else{
rson.pb(val[i]);
if(val[i].se) chn.pb(val[i].se);
}
// cout<<pl<<' ';
}
// cout<<endl;
for(auto r:vec) if(r.se>mid) rson.pb(r);
// cout<<"lson "<<lson.size()<<' '<<rson.size()<<' '<<all<<endl;
for(auto r:chn) add(r,1);
solve(l,mid,lson,sum);
for(auto r:chn) add(r,-1);
solve(mid+1,r,rson,sum+rval);
}
int main(){
n=readint();
for(int i=1;i<=n;i++) px[++nx]=a[i].fi=readint(),py[++ny]=a[i].se=readint();
m=readint();
for(int i=1;i<=m;i++) px[++nx]=b[i].fi=readint(),py[++ny]=b[i].se=readint();
sort(px+1,px+nx+1);
nx=unique(px+1,px+nx+1)-px-1;
sort(py+1,py+ny+1);
ny=unique(py+1,py+ny+1)-py-1;
for(int i=1;i<=n;i++){
a[i].fi=lower_bound(px+1,px+nx+1,a[i].fi)-px;
a[i].se=lower_bound(py+1,py+ny+1,a[i].se)-py;
}
for(int i=1;i<=m;i++){
b[i].fi=lower_bound(px+1,px+nx+1,b[i].fi)-px;
b[i].se=lower_bound(py+1,py+ny+1,b[i].se)-py;
}
vector<pair<pii,int> > vec;
for(int i=1;i<=n;i++) vec.pb(mp(a[i],0));
for(int i=1;i<=m;i++) vec.pb(mp(b[i],i));
solve(1,m,vec,0);
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 7860kb
input:
3 0 0 1 1 2 2 4 0 0 1 1 0 0 3 3
output:
1 2 2 3
result:
ok 4 number(s): "1 2 2 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 7868kb
input:
9 22 44 7 6 10 48 46 20 21 35 33 16 36 41 29 4 45 22 7 46 39 44 32 1 48 43 19 28 34 8 48 15 18
output:
1 2 2 3 4 4 4
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 7780kb
input:
7 25 13 38 45 30 28 28 29 16 34 45 4 47 13 8 24 16 10 18 8 28 40 47 28 35 5 25 29 0 41 17
output:
0 0 0 1 2 2 2 3
result:
ok 8 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 9700kb
input:
10 47 32 0 16 18 11 17 19 40 49 36 24 3 26 15 45 23 29 42 3 5 42 18 22 3 30 13 35 19 43 29
output:
1 1 2 3 4
result:
ok 5 number(s): "1 1 2 3 4"
Test #5:
score: 0
Accepted
time: 3ms
memory: 9952kb
input:
6 2 5 22 3 28 41 41 36 9 8 8 17 2 24 7 49 35
output:
1 2
result:
ok 2 number(s): "1 2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 9832kb
input:
2 27 36 5 39 6 47 22 45 4 44 2 24 2 29 11 21 37
output:
0 0 0 0 0 0
result:
ok 6 numbers
Test #7:
score: -100
Wrong Answer
time: 3ms
memory: 7800kb
input:
30 35 14 26 38 50 17 21 0 14 0 39 2 5 45 1 18 22 50 5 49 35 16 37 43 15 11 22 16 4 9 44 36 1 23 42 19 33 44 2 44 35 16 21 36 23 46 39 1 15 29 9 17 31 27 37 50 15 24 30 38 48 10 38 28 0 33 5 33 11 36 27 4 30 4 18 23 28 4 8 16 20 24 47 14 34 30 45 47 10 4 48 36 2 10 20 11 39 49 39 11 50 48 36 28 41 23...
output:
1 2 3 4 5 6 7 8 8 9 10 10 11 12 13 13 13 13 14 15 16 17 17 17 18 18 19 20 21 22 22 22 22 22 22 22 23 23 23 23 24 24 24 25 26 26 26 26
result:
wrong answer 31st numbers differ - expected: '23', found: '22'