제출 #927823

#제출 시각아이디문제언어결과실행 시간메모리
927823hqminhuwuExamination (JOI19_examination)C++14
100 / 100
1536 ms28312 KiB
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
const int uwu = 317;

pair <pii, pii> w[N];
int bit[uwu + 5][uwu + 5], n, q, i, j, k, ans[N], flag[N];
pii a[N];
vector <pii> f;
vi v[N];

void update (int id, int x){
	for (; x > 0; x -= x & -x)
		bit[id][x]++;
}

int get (int id, int x){
	int res = 0;
	for (; x <= uwu + 1; x += x & -x)
		res += bit[id][x];
	return res;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	#ifdef hqm
	   freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
	#endif

	cin >> n >> q;
	
	forr (i, 1, n)
		cin >> a[i].st >> a[i].nd;
	
	sort(a + 1, a + 1+ n);
	
	forr (i, 1, n)
		f.pb({a[i].st + a[i].nd, i});
	
	forr (i, 1, n)
		v[i / uwu].pb(a[i].nd);

	forr (i, 0, n / uwu){
		sort(all(v[i])), v[i].erase(unique(all(v[i])), v[i].end());
	}

	forr (i, 1, q)
		cin >> w[i].nd.st >> w[i].nd.nd >> w[i].st.st, w[i].st.nd = i;
	
	sort(w + 1, w + 1 + n, greater<pair<pii, pii>>());
	sort(all(f));

	int it = f.size() - 1;

	forr (i, 1, q){
		int z = w[i].st.st, x = w[i].nd.st, y = w[i].nd.nd, pos = w[i].st.nd;
		while (it >= 0 && f[it].st >= z){
			int id = f[it].nd / uwu;
			flag[f[it].nd] = 1;
			int tmp = lower_bound(all(v[id]), a[f[it].nd].nd) - v[id].begin() + 1;
			//cout << f[it].st << " " << a[f[it].nd].st << " " << a[f[it].nd].nd << " " << id << " " << tmp << "\n";
			update(id, tmp);
			it--;
		}

		int j = n / uwu;
		while (j >= 0 && a[uwu * j].st >= x){
			int e = lower_bound(all(v[j]), y) - v[j].begin() + 1;
		//	cout << e << "\n";
			ans[pos] += get(j, e);
			j--;
		}

		if (j >= 0)
		ford (k, uwu * (j + 1) - 1, j * uwu){
			ans[pos] += (y <= a[k].nd && x <= a[k].st) * flag[k];
		}
	//	cout << y << "\n";
	}

	forr (i, 1, q)
		cout << ans[i] << "\n";
	return 0;
}
/*



*/

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...