Submission #461352

#	Time	Username	Problem	Language	Result	Execution time	Memory
461352		zaneyu	Examination (JOI19_examination)	C++14	100 / 100	470 ms	76264 KiB

examination

 /*input
7 7
10000 100
70 70
45 15
2000 40
2000 95800 
6 70000
8000 10000
20 30000 0
2000 10 0
80 2999 0
0 100 0
70 600 0
1000 1000 0
4900 3500 0
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld double
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=1e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
ll mult(ll a,ll b){
    return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
pii arr[maxn];
pair<pii,pii> query[maxn];
struct node{
    ll sum=0;
    int lc=0,rc=0;
}seg[40*maxn];
//check this line
int tot=2;
inline void mdf(int &idx,ll l,ll r,int p,int x){
    if(r<p or l>p) return;
    if(!idx){
        idx=(tot++);
    }
    if(l==r){
        seg[idx].sum+=x;
        return;
    }
    int mid=(l+r)/2;
    mdf(seg[idx].lc,l,mid,p,x);
    mdf(seg[idx].rc,mid+1,r,p,x);
    seg[idx].sum=(seg[seg[idx].lc].sum+seg[seg[idx].rc].sum);
}
inline ll qq(int &idx,ll l,ll r,int ql,int qr){
    if(!idx){
        return 0;
    }
    if(r<ql or l>qr) return 0;
    if(ql<=l and r<=qr){
        return seg[idx].sum;
    }
    int mid=(l+r)/2;
    return (qq(seg[idx].lc,l,mid,ql,qr)+qq(seg[idx].rc,mid+1,r,ql,qr));
}
int rt=1;
inline void mdf(int p,int x){
	mdf(rt,0,2e9,p,x);
}
inline int qq(int l,int r){
	return qq(rt,0,2e9,l,r);
}
int ans[maxn];
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,q;
    cin>>n>>q;
    //vector<int> dx,dy,dz;
    multiset<pii> stf;
    REP(i,n) cin>>arr[i].f>>arr[i].s,stf.insert({arr[i].s,arr[i].s+arr[i].f});
    vector<pair<pii,pii>> query,qb;

    REP(i,q){
    	pair<pii,pii> x;
    	cin>>x.f.f>>x.f.s>>x.s.f;
    	x.s.s=i;
    	if(x.f.f+x.f.s>=x.s.f) query.pb(x);
    	else qb.pb(x);
    }
    sort(ALL(query));
    sort(arr,arr+n);
    int p=n-1;
    for(int i=sz(query)-1;i>=0;i--){
    	while(p>=0 and arr[p].f>=query[i].f.f) mdf(2e9-arr[p].s,1),--p;
    	ans[query[i].s.s]=qq(0,2e9-query[i].f.s);
    }
  	sort(ALL(qb));
    REP(i,40*maxn) seg[i].sum=seg[i].lc=seg[i].rc=0;
    tot=2;
    p=n-1;
 	for(int i=sz(qb)-1;i>=0;i--){
    	while(p>=0 and arr[p].f>=qb[i].f.f) mdf(2e9-arr[p].s-arr[p].f,1),--p;
    	ans[qb[i].s.s]=qq(0,2e9-qb[i].s.f);
    	//cout<<qb[i].s.s<<' '<<ans[qb[i].s.s]<<'\n';
 	}
 	REP(i,40*maxn) seg[i].sum=seg[i].lc=seg[i].rc=0;
 	tot=2;
 	REP(i,n) swap(arr[i].f,arr[i].s);
 	sort(arr,arr+n);
 	REP(i,sz(qb)){
 		swap(qb[i].f.f,qb[i].f.s);
 	}
  	sort(ALL(qb));
  	p=0;
  	REP(i,sz(qb)){
    	while(p<n and arr[p].f<qb[i].f.f) mdf(2e9-arr[p].s-arr[p].f,1),++p;
    	ans[qb[i].s.s]-=qq(0,2e9-qb[i].s.f);
 	}
    REP(i,q) cout<<ans[i]<<'\n';
} 

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57