Submission #613393

#	Time	Username	Problem	Language	Result	Execution time	Memory
613393		amunduzbaev	Examination (JOI19_examination)	C++17	43 / 100	3093 ms	120332 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;

template<class T> using oset = tree<T, null_type, less_equal<T>, 
rb_tree_tag, tree_order_statistics_node_update>;

#define ar array
typedef int64_t ll;
#define sow cerr<<"here"<<endl;

const int N = 1e5 + 5;

struct ST{
	oset<int> tree[N << 2];
	void add(int i, int v, int lx = 0, int rx = N, int x = 1){
		tree[x].insert(v);
		if(lx == rx) return;
		int m = (lx + rx) >> 1;
		if(i <= m) add(i, v, lx, m, x << 1);
		else add(i, v, m + 1, rx, x << 1 | 1);
	}
	
	int get(int l, int v, int lx = 0, int rx = N, int x = 1){
		if(rx < l) return 0;
		if(lx >= l){
			return tree[x].size() - tree[x].order_of_key(v);
		} int m = (lx + rx) >> 1;
		return get(l, v, lx, m, x << 1) + get(l, v, m + 1, rx, x << 1 | 1);
	}
}T;

int s[N], t[N], x[N], y[N], z[N], res[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q; cin >> n >> q;
	vector<int> P(n), zh;
	for(int i=0;i<n;i++){
		cin >> s[i] >> t[i];
		P[i] = i;
		zh.push_back(t[i]);
	}
	
	sort(zh.begin(), zh.end());
	zh.erase(unique(zh.begin(), zh.end()), zh.end());
	
	vector<int> p(q);
	for(int i=0;i<q;i++){
		cin >> x[i] >> y[i] >> z[i];
		p[i] = i;
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return x[i] > x[j];
	});
	sort(P.begin(), P.end(), [&](int i, int j){
		return s[i] > s[j];
	});
	
	auto add = [&](int i){
		int x = lower_bound(zh.begin(), zh.end(), t[i]) - zh.begin();
		T.add(x, s[i] + t[i]);
		//~ sow
	};
	
	int j = 0;
	for(auto i : p){
		while(j < n && s[P[j]] >= x[i]){
			add(P[j++]);
		}
		int k = lower_bound(zh.begin(), zh.end(), y[i]) - zh.begin();
		res[i] = T.get(k, z[i]);
	}
	
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}

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