QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#33724 | #4219. Insects | he_____he | WA | 4ms | 9864kb | C++ | 3.0kb | 2022-06-04 18:56:02 | 2022-06-04 18:56:04 |
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(){
// freopen("black.in","r",stdin);
// freopen("black.out","w",stdout);
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;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 9864kb
input:
3 0 0 1 1 2 2 4 0 0 1 1 0 0 3 3
output:
0 1 1 2
result:
wrong answer 1st numbers differ - expected: '1', found: '0'