제출 #810775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810775		OrazB	Examination (JOI19_examination)	C++14	0 / 100	3054 ms	29084 KiB

examination

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
#define pii pair <int, int>
// #define ordered_set tree<pair<pii,int>, null_type,less<pair<pii,int>>, rb_tree_tag,tree_order_statistics_node_update>
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pb push_back
#define ff first
#define ss second

const int N = 1e6;
const int M = 1e5;
int n, q;
int pos[N], s[N], t[N], ans[N];
int x[N], y[N], z[N], ind[N];
int f[N][2];
vector<int> E[N];


void add(int x, int y){
	for (int i = x; i <= M; i += i&(-i)){
		f[i][0]++;
	}
	for (int i = y; i <= M; i += i&(-i)){
		f[i][1]++;
	}
	for (int i = x; i <= M; i += i&(-i)){
		E[i].pb(y);
	}
}
int count(int x, int y){
	int cnt = 0;
	for (int i = x; i > 0; i -= i&(-i)){
		cnt += f[i][0];
	}
	for (int i = y; i > 0; i -= i&(-i)){
		cnt += f[i][1];
	}
	for (int i = x; i > 0; i -= i&(-i)){
		int l = 0, r = E[i].size()-1, pos = -1;
		while(l <= r){
			int md = (l+r)>>1;
			if (E[i][md] > y) r = md - 1;
			else{
				pos = md;
				l = md + 1;
			}
		}
		cnt -= pos+1;
	}
	return cnt;
}

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++){
		cin >> s[i] >> t[i];
		add(s[i], t[i]);
		// pos[i] = i;
	}
	for (int i = 1; i <= M; i++) sort(all(E[i]));
	// sort(pos+1,pos+n+1, [&](int x, int y){
	// 	return (s[x]+t[x]) > (s[y]+t[y]); 
	// });
	for (int i = 1; i <= q; i++){
		cin >> x[i] >> y[i] >> z[i];
		cout << n-count(x[i]-1, y[i]-1) << '\n';
		// ind[i] = i;
	}
	// sort(ind+1,ind+q+1, [&](int x, int y){
	// 	return z[x] > z[y]; 
	// });
	// int l = 0;
	// for (int i = 1; i <= q; i++){
	// 	while(l < n and s[pos[l+1]]+t[pos[l+1]] >= z[ind[i]]){
	// 		l++;
	// 		add(s[pos[l]], t[pos[l]]);
	// 	}
	// 	ans[ind[i]] = l-count(x[ind[i]]-1, y[ind[i]]-1);
	// }
	// for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}	

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