Submission #1089823

#TimeUsernameProblemLanguageResultExecution timeMemory
1089823HienTDExamination (JOI19_examination)C++14
2 / 100
3054 ms3196 KiB
#include <bits/stdc++.h>
using namespace std;

//#define LOCAL

//#define USACO

#define          	fi  first
#define             se  second
#define           TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define         ALL(v)  (v).begin(), (v).end()
#define  		BIT(x)  (1LL << (x))
#define 	MASK(x, i)  (((x) >> (i)) & 1)
#define   FOR(i, a, b)  for(int i = (a), _b = (b); i <= _b; ++ i)
#define  FORD(i, b, a)  for(int i = (b), _a = (a); i >= _a; -- i)

const string NAME = "BAITAP";

const string name = "";

const long long INF = 1e18;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int mod = 998244353;

const int mxN = 1e5 + 5;

struct candinate{
	int A, B, C;
	candinate() : A(0), B(0), C(0){};
	candinate(int A, int B) : A(A), B(B), C(A + B){};
};

int N, Q;
vector<candinate> st(mxN);

void init(void){
	cin >> N >> Q;
	FOR(i, 1, N){
		int a, b;
		cin >> a >> b;
		st[i] = candinate(a, b);
	}
}

struct cmp{
	bool operator() (const candinate &a, const candinate &b){
		return a.C < b.C;
	}
};

int cnp(const int &x){
	int lo = 0;
	int hi = N + 1;
	while(hi - lo > 1){
		int mid = (lo + hi) >> 1;
		if(st[mid].C >= x) hi = mid;
		else lo = mid;
	}
	return hi;
}

void process(void){
	sort(st.begin() + 1, st.begin() + 1 + N, cmp());
	//FOR(i, 1, N) cout << i << ' ' << st[i].A << ' ' << st[i].B << ' ' << st[i].C << '\n';
	while(Q --){
		int a, b, c;
		cin >> a >> b >> c;
		int pos = cnp(c);
		int cnt = 0;
		FOR(i, pos, N) if(st[i].A >= a && st[i].B >= b && st[i].C >= c) ++ cnt;
		cout << cnt << '\n';
	}
}

signed main(void){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	#ifdef LOCAL
		freopen((NAME + ".INP").c_str(), "r", stdin);
		freopen((NAME + ".OUT").c_str(), "w", stdout);
	#elif defined(USACO)
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	#endif // I/O

	init();
	process();
	cerr << "\nTime elapsed: " << TIME << "s.\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...