Submission #482465

#	Time	Username	Problem	Language	Result	Execution time	Memory
482465		S2speed	Examination (JOI19_examination)	C++17	100 / 100	174 ms	19004 KiB

examination

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 1e5 + 16 , md = 1e9 + 7 , inf = 2e16;

ll gcd(ll a , ll b){
	if(a < b) swap(a , b);
	if(b == 0) return a;
	return gcd(b , a % b);
}

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

struct fentree {

	ll sz;
	vector<ll> val;

	void init(ll n){
		sz = n;
		val.assign(sz , 0);
		return;
	}

	void add(ll i){
		ll h = i;
		while(h < sz){
			val[h]++;
			h |= (h + 1);
		}
		return;
	}

	ll cal(ll i){
		ll res = 0 , h = i;
		while(h > -1){
			res += val[h];
			h &= (h + 1); h--;
		}
		return res;
	}

	void clear(){
		val.clear();
		return;
	}

};

ll a[maxn] , b[maxn] , ap[maxn] , bp[maxn] , x[maxn] , y[maxn] , z[maxn] , ans[maxn];
vector<pll> t , r , v;
vector<ll> ca , cb;
fentree s , f;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	ll n , q;
	cin>>n>>q;
	for(ll i = 0 ; i < n ; i++){
		cin>>a[i]>>b[i];
		v.push_back({a[i] + b[i] , i});
	}
	for(ll i = 0 ; i < n ; i++){
		ca.push_back(a[i]);
	}
	sort(all(ca));
	ca.resize(distance(ca.begin() , unique(all(ca))));
	for(ll i = 0 ; i < n ; i++){
		ap[i] = lower_bound(all(ca) , a[i]) - ca.begin();
	}
	for(ll i = 0 ; i < n ; i++){
		cb.push_back(b[i]);
	}
	sort(all(cb));
	cb.resize(distance(cb.begin() , unique(all(cb))));
	for(ll i = 0 ; i < n ; i++){
		bp[i] = lower_bound(all(cb) , b[i]) - cb.begin();
	}
	for(ll i = 0 ; i < q ; i++){
		cin>>x[i]>>y[i]>>z[i];
		if(x[i] + y[i] >= z[i]){
			t.push_back({y[i] , i});
		} else {
			r.push_back({z[i] , i});
		}
	}
	sort(all(r) , greater<pll>());
	sort(all(v) , greater<pll>()); v.push_back({-1 , -1});
	ll p = 0;
	s.init(n); f.init(n);
	for(auto u : r){
		while(v[p].first >= u.first){
			ll j = v[p++].second;
			s.add(ap[j]); f.add(bp[j]);
		}
		ll i = u.second , j = lower_bound(all(ca) , x[i]) - ca.begin() - 1;
		ans[i] = p - s.cal(j);
		j = lower_bound(all(cb) , y[i]) - cb.begin() - 1;
		ans[i] -= f.cal(j);
	}
	s.clear();
	v.clear();
	p = 0;
	for(ll i = 0 ; i < n ; i++){
		v.push_back({b[i] , i});
	}
	sort(all(t) , greater<pll>());
	sort(all(v) , greater<pll>()); v.push_back({-1 , -1});
	s.init(n);
	for(auto u : t){
		while(v[p].first >= u.first){
			ll j = v[p++].second;
			s.add(ap[j]);
		}
		ll i = u.second , j = lower_bound(all(ca) , x[i]) - ca.begin() - 1;
		ans[i] = p - s.cal(j);
	}
	for(ll i = 0 ; i < q ; i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

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