Submission #997851

#	Time	Username	Problem	Language	Result	Execution time	Memory
997851		cnn008	Examination (JOI19_examination)	C++17	0 / 100	3061 ms	14828 KiB

examination

#include "bits/stdc++.h"
using namespace std;

#ifdef N_N_C
#include "debug.h"
#else
#define cebug(...) "Arya"
#endif

#define int long long

const int N=1e5+5;
const int mod=1e9+7;

struct Point{
	int x,y,z,id;
	bool operator < (const Point &o){
		if(x==o.x){
			if(y==o.y) return z>o.z;
			return y>o.y;
		}
		return x>o.x;
	}
};
vector <Point> v,v1;
int n,q,ans[N],ans1[N];
struct BIT{
	#define gb(x) (x&(-x))
   	int n;
   	vector <int> bit;
   	void init(int _n){
   		bit.resize(_n,0);
   		n=_n;
   	}
   	void update(int pos, int val){
   		int i=pos;
      	for (; i; i-=gb(i)) bit[i]+=val;
   	}
   	int get(int pos){
    	int ans=0,i=pos;
      	for (; i<n; i+=gb(i)) ans+=bit[i];
      	return ans;
   	}
}fw;
void cdq(int l, int r){
	if(l+1==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid,r);
	vector <Point> tmp;
	vector <int> record;
	int a=l,b=mid;
	while(a<mid and b<r){
		if(v[a].y>=v[b].y) fw.update(v[a].z,1),record.push_back(v[a].z),tmp.push_back(v[a++]);
		else ans[v[b].id]+=fw.get(v[b].z),tmp.push_back(v[b++]); 
	}
	while(a<mid) tmp.push_back(v[a++]);
	while(b<r) ans[v[b].id]+=fw.get(v[b].z),tmp.push_back(v[b++]);
	for(int i=l; i<r; i++) v[i]=tmp[i-l];
	for(auto x:record) fw.update(x,-1);
	vector <int> ().swap(record);
	vector <Point> ().swap(tmp);
}
void cdq1(int l, int r){
	if(l+1==r) return;
	int mid=(l+r)>>1;
	cdq1(l,mid);
	cdq1(mid,r);
	vector <Point> tmp;
	vector <int> record;
	int a=l,b=mid;
	while(a<mid and b<r){
		if(v1[a].y>=v1[b].y) fw.update(v1[a].z,1),record.push_back(v1[a].z),tmp.push_back(v1[a++]);
		else ans1[v1[b].id]+=fw.get(v1[b].z),tmp.push_back(v1[b++]); 
	}
	while(a<mid) tmp.push_back(v1[a++]);
	while(b<r) ans1[v1[b].id]+=fw.get(v1[b].z),tmp.push_back(v1[b++]);
	for(int i=l; i<r; i++) v1[i]=tmp[i-l];
	for(auto x:record) fw.update(x,-1);
	vector <int> ().swap(record);
	vector <Point> ().swap(tmp);
}
void sol(){
	// count pair i j : i_x<j_x, i_x<j_y, i_z<j_z
	fw.init(N);
	cin>>n>>q;
	for(int i=1; i<=n; i++){
		int x,y;
		cin>>x>>y;
		v.push_back({x,y,x+y,i});
	}
	for(int i=1; i<=q; i++){
		int x,y,z;
		cin>>x>>y>>z;
		v.push_back({x,y,z,n+i});
		v1.push_back({x,y,z,n+i});
	}
	sort(v.begin(),v.end());
	cdq(0,(int)v.size());
	sort(v1.begin(),v1.end());
	cdq1(0,(int)v1.size());
	for(int i=n+1; i<=n+q; i++) cout<<ans[i]-ans1[i]<<"\n";
}
signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);
    int tt=1;
    //cin>>tt; 
    while(tt--){
    	sol();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}

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