Submission #1056634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056634		vako_p	Examination (JOI19_examination)	C++14	100 / 100	315 ms	68796 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e5 + 5;
ll n,q;
pair<ll,ll> a[mxN];
vector<pair<ll,ll>> vv;

struct bt{
	vector<vector<ll>> v,v1;
	ll sz = 1; 
	
	void init(){
		while(sz < n) sz *= 2;
		v.resize(2 * sz);
		v1.resize(2 * sz);
		for(int i = sz - 1; i < 2 * sz - 1; i++){
			if(i - sz + 1 < n){
				v[i].pb(a[i - sz + 1].first + a[i - sz + 1].second);
				v1[i].pb(a[i - sz + 1].second);
			}
			else{
				v[i].pb(0);
				v1[i].pb(0);
			}
		}
		for(int x = sz - 2; x >= 0; x--){
			ll l = 0;
			for(int i = 0; i < v[2 * x + 1].size(); ){
				if(l >= v[2 * x + 2].size()){
					v[x].pb(v[2 * x + 1][i++]);
					continue;
				}
				if(v[2 * x + 2][l] <= v[2 * x + 1][i]) v[x].pb(v[2 * x + 2][l++]);
				else v[x].pb(v[2 * x + 1][i++]);
			}
			for( ; l < v1[2 * x + 2].size(); l++) v[x].pb(v[2 * x + 2][l]);
			l = 0;
			for(int i = 0; i < v1[2 * x + 1].size(); ){
				if(l >= v1[2 * x + 2].size()){
					v1[x].pb(v1[2 * x + 1][i++]);
					continue;
				}
				if(v1[2 * x + 2][l] <= v1[2 * x + 1][i]) v1[x].pb(v1[2 * x + 2][l++]);
				else v1[x].pb(v1[2 * x + 1][i++]);
			}
			for( ; l < v1[2 * x + 2].size(); l++) v1[x].pb(v1[2 * x + 2][l]);
		}
	}
	
	ll find(ll val, ll l, ll r, ll x, ll lx, ll rx){
		if(lx >= r or rx <= l) return 0LL;
		if(lx >= l and rx <= r){
			auto it = lower_bound(v[x].begin(), v[x].end(), val);
			ll dis = it - v[x].begin(), siz = v[x].size();
			return (siz - dis);
		}
		ll mid = lx + (rx - lx) / 2;
		return (find(val, l, r, 2 * x + 1, lx, mid) + find(val, l, r, 2 * x + 2, mid, rx));
	}
	
	ll find(ll val, ll l, ll r){
		return find(val, l, r, 0, 0, sz);
	}
	
	ll find1(ll val, ll l, ll r, ll x, ll lx, ll rx){
		if(lx >= r or rx <= l) return 0LL;
		if(lx >= l and rx <= r){
			auto it = lower_bound(v1[x].begin(), v1[x].end(), val);
			ll dis = it - v1[x].begin(), siz = v1[x].size();
			return (siz - dis);
		}
		ll mid = lx + (rx - lx) / 2;
		return (find1(val, l, r, 2 * x + 1, lx, mid) + find1(val, l, r, 2 * x + 2, mid, rx));
	}
	
	ll find1(ll val, ll l, ll r){
		return find1(val, l, r, 0, 0, sz);
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	bt s;
	for(int i = 0; i < n; i++){
		cin >> a[i].first >> a[i].second;
	}
	sort(a, a + n);
	s.init();
	vv.pb({a[0].first, 0});
	for(int i = 1; i < n; i++) if(a[i].first != a[i - 1].first) vv.pb({a[i].first, i}); 
	while(q--){
		ll A,B,C;
		cin >> A >> B >> C;
		pair<ll,ll> xx = {A, 0};
		auto it = lower_bound(vv.begin(), vv.end(), xx);
		if(it == vv.end()){
			cout << 0 << '\n';
			continue;
		}
		if(A + B >= C){
			cout << s.find1(B, (*it).second, n) << '\n';
		}  
		else{
			ll A1 = C - B;
			xx = {A1, 0};
			auto it1 = lower_bound(vv.begin(), vv.end(), xx);
			if(it1 == vv.end()) cout << s.find(C, (*it).second, n) << '\n';
			else cout << s.find(C, (*it).second, (*it1).second) + s.find1(B, (*it1).second, n)<< '\n';
		}
	}
}

Compilation message (stderr)

examination.cpp: In member function 'void bt::init()':
examination.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    for(int i = 0; i < v[2 * x + 1].size(); ){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~
examination.cpp:32:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     if(l >= v[2 * x + 2].size()){
      |        ~~^~~~~~~~~~~~~~~~~~~~~~
examination.cpp:39:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for( ; l < v1[2 * x + 2].size(); l++) v[x].pb(v[2 * x + 2][l]);
      |           ~~^~~~~~~~~~~~~~~~~~~~~~
examination.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    for(int i = 0; i < v1[2 * x + 1].size(); ){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
examination.cpp:42:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     if(l >= v1[2 * x + 2].size()){
      |        ~~^~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:49:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    for( ; l < v1[2 * x + 2].size(); l++) v1[x].pb(v1[2 * x + 2][l]);
      |           ~~^~~~~~~~~~~~~~~~~~~~~~

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