Cod sursa(job #2496156)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 20 noiembrie 2019 12:06:13
Problema Ograzi Scor 10
Compilator cpp-64 Status done
Runda casiaiziscanudaisimulareprimaora Marime 2.75 kb
#define up(x) x & -x
#include <algorithm>
#include <iostream>
#include <vector>
#include <fstream>
#include <cstdio>
using namespace std;



const int MAXN = 1e5 + 5;
int n,m,w,h;
pair < int, int > a[MAXN];
vector < int > bx,by;
vector < int > puncte[MAXN];
struct plm {
	
	int x1,y1,x2,y2;
}drept[MAXN*2];
int ans[MAXN * 3];
struct PLM{
	
	int x,y,type,d;
	bool operator < (const PLM & next) const {
		
		return ((x < next.x) or (x == next.x and type > next.type));
	} 
};
vector < PLM > querys;
int aib[MAXN*2];
void Get(int & x) ;

void update(int poz) {
	
	for ( int i = poz; i < MAXN * 2; i += up(i))
		aib[i] ++;
}

int query(int poz){
	
	int ans = 0;
	for ( int i = poz; i >= 1; i -= up(i))
		ans += aib[i];
	return ans;
	
}


int main() {
	
	freopen("ograzi.in","r",stdin);
	freopen("ograzi.out","w",stdout);
	Get(n);Get(m);Get(w); Get(h);
	for ( int i = 1; i <= n; ++i) {
		
		Get(drept[i].x2); Get(drept[i].y1);
		bx.push_back(drept[i].x2);
		by.push_back(drept[i].y1);
		drept[i].x1 = drept[i].x2 + w - 1;
		drept[i].y2 = drept[i].y1 + h - 1;
		bx.push_back(drept[i].x1);
		by.push_back(drept[i].y2);
		
	}
	for ( int i = 1; i <= m; ++i) {
		Get(a[i].first); Get(a[i].second);
		bx.push_back(a[i].first);
		by.push_back(a[i].second);
	}
	sort(bx.begin(),bx.end());
	bx.erase(unique(bx.begin(),bx.end()),bx.end());
	sort(by.begin(),by.end());
	by.erase(unique(by.begin(),by.end()),by.end());
	for ( int i = 1; i <= m; ++i) {
		a[i].first = lower_bound(bx.begin(),bx.end(),a[i].first) - bx.begin() + 2;
		a[i].second = lower_bound(by.begin(),by.end(),a[i].second) - by.begin() + 2;
		
	}
	for ( int i = 1; i <= n; ++i) {
		drept[i].x1 = (int)(lower_bound(bx.begin(),bx.end(),drept[i].x1) - bx.begin() + 2);
		drept[i].x2 = (int)(lower_bound(bx.begin(),bx.end(),drept[i].x2) - bx.begin() + 2);
		drept[i].y1 = (int)(lower_bound(by.begin(),by.end(),drept[i].y1) - by.begin() + 2);
		drept[i].y2 = (int)(lower_bound(by.begin(),by.end(),drept[i].y2) - by.begin() + 2);	
		
	}
	for ( int i = 1; i <= n; ++i) {
		querys.push_back({drept[i].x1,drept[i].y2,1,i});
		querys.push_back({drept[i].x1,drept[i].y1-1,-1,i});
		querys.push_back({drept[i].x2-1,drept[i].y2,-1,i});
		querys.push_back({drept[i].x2-1,drept[i].y1-1,+1,i});
	}
	for ( int i = 1; i <= m; ++i)
		querys.push_back({a[i].first,a[i].second,3,i});	
	
	sort(querys.begin(),querys.end());
	for ( auto y : querys) {
		if ( y.type != 3) {
		ans[y.d] += (y.type * query(y.y));
			
			}
		else
			update(y.y);
	}
	int s = 0;
	for ( int i = 1; i <= n; ++i)
		s += ans[i];
	printf("%d",s);
	
}

const int Lim = 100001;
int u = Lim-1;
char t[Lim+1];

void Next() {

	if (++u == Lim)
		fread(t,1,Lim,stdin),u = 0;
}

void Get(int & x) {
	
	x = 0;
	for (;t[u] < '0' or t[u] > '9'; Next());
	for (;t[u] >= '0' and t[u] <= '9'; Next())
		x = x*10 + t[u] -'0'; 
}