Submission #1158419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158419		zhasyn	Examination (JOI19_examination)	C++20	2 / 100	364 ms	79156 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define pf push_front
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1e5 + 100, M = 1e5 + 100, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
ll um(ll a, ll b){
	return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>o_set;
int a[N], b[N], sz, ans[N], timer;
o_set st[M];
int lt[M], rt[M];
int create(){
	int v = timer++;
	lt[v] = rt[v] = -1;
	return v;
}
struct seg {
	void init(int n){
		sz = 1;
		while(sz < n) sz *= 2;
	}
	void upd(int i, int v, int x = 0, int lx = 0, int rx = sz){
	    //cout << x << " " << lx << " "<< rx << " here\n";
	    st[x].insert(v);
		if(rx - lx == 1){
            //cout << lx << " "<< rx << " End up here\n";
            return;
		}
		int mid = (lx + rx) / 2;
		if(i < mid) {
			if(lt[x] == -1) lt[x] = create();
			upd(i, v, lt[x], lx, mid);
		} else {
			if(rt[x] == -1) rt[x] = create();
			upd(i, v, rt[x], mid, rx);
		}
	}
	int get(int l, int r, int y, int x = 0, int lx = 0, int rx = sz){
		if(l >= rx || lx >= r) return 0;
		if(l <= lx && rx <= r){
            // get answer
            //cout << lx << " "<< rx << " " << (int)st[x].size() - st[x].order_of_key(y) << " Ranges\n";
			return (int)st[x].size() - st[x].order_of_key(y);
		}
		int mid = (lx + rx) / 2, cur = 0;
		if(lt[x] != -1) cur += get(l, r, y, lt[x], lx, mid);
		if(rt[x] != -1) cur += get(l, r, y, rt[x], mid, rx);
		return cur;
	}
};
int main(){
	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	int n, q;
  	cin >> n >> q;
  	create();
  	seg obj;
  	obj.init(1e9 + 5);
  	vector <pair <pii, pii> > vec, ps;
  	for(int i = 0; i < n; i++){
  		cin >> a[i] >> b[i];
  		ps.pb(make_pair(make_pair(a[i] + b[i], i), make_pair(a[i], b[i])));
	}
	for(int i = 0, x, y, z; i < q; i++){
		cin >> x >> y >> z;
		vec.pb(make_pair(make_pair(z, i), make_pair(x, y)));
	}
	sort(vec.begin(), vec.end());
	sort(ps.begin(), ps.end());
	for(int i = (int)vec.size() - 1, x, y, z, code; i >= 0; i--){
		x = vec[i].S.F;
		y = vec[i].S.S;
		code = vec[i].F.S;
		z = vec[i].F.F;
		//cout << code << " "<< x << " "<< y << " "<< z << " OP\n";
		while((int)ps.size() != 0){
			pair <pii, pii> v = ps.back();
			if(v.F.F >= z){
                //cout << v.S.F << " "<< v.S.S << " was added\n";
				obj.upd(v.S.F, v.S.S);
				ps.pop_back();
			} else break;
		}
        ans[code] = obj.get(x, 1e9 + 1, y);
	}
	for(int i = 0; i < q; i++){
		cout << ans[i] << endl;
	}
	return 0;
}

/*
5 1
35 100
70 70
45 15
80 40
20 95
10 10 100
*/

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