Submission #613485

#	Time	Username	Problem	Language	Result	Execution time	Memory
613485		amunduzbaev	Examination (JOI19_examination)	C++17	100 / 100	1719 ms	56124 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 node{
	//~ int sum, L, R;
	//~ node(){
		//~ sum = L = R = 0;
	//~ }
//~ };

//~ struct ST{
	//~ vector<node> tree;
	//~ int last;
	//~ ST(){
		//~ last = 1;
		//~ tree.resize(1);
	//~ }
	
	//~ void pot(int x){
		//~ if(!tree[x].L) tree[x].L = last++, tree.resize(last);
		//~ if(!tree[x].R) tree[x].R = last++, tree.resize(last);
	//~ }
	
	//~ void add(int i, int v, int lx = 0, int rx = N, int x = 0){
		//~ if(lx == rx){
			//~ tree[x].sum += v;
			//~ return;
		//~ } int m = (lx + rx) >> 1;
		//~ pot(x);
		//~ if(i <= m) add(i, v, lx, m, tree[x].L);
		//~ else add(i, v, m + 1, rx, tree[x].R);
		//~ tree[x].sum = tree[tree[x].L].sum + tree[tree[x].R].sum;
	//~ }
	
	//~ int get(int l, int r, int lx = 0, int rx = N, int x = 0){
		//~ if(lx > r || rx < l) return 0;
		//~ if(lx >= l && rx <= r) return tree[x].sum;
		//~ int m = (lx + rx) >> 1, res = 0;
		//~ if(tree[x].L) res += get(l, r, lx, m, tree[x].L);
		//~ if(tree[x].R) res += get(l, r, m + 1, rx, tree[x].R);
		//~ return res;
	//~ }
//~ };

struct BIT{
	oset<int> tree[N];
	void add(int i, int v){
		i = N - i - 1;
		for(;i<N;i+=(i&-i)) tree[i].insert(v);
	}
	
	int get(int i, int v){
		int r = 0; i = N - i - 1;
		for(;i>0;i-=(i&-i)) r += (tree[i].size() - tree[i].order_of_key(v));
		return r;
	}
}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, zhs;
	for(int i=0;i<n;i++){
		cin >> s[i] >> t[i];
		P[i] = i;
		zh.push_back(t[i]);
		zhs.push_back(s[i] + t[i]);
	}
	
	sort(zh.begin(), zh.end());
	zh.erase(unique(zh.begin(), zh.end()), zh.end());
	sort(zhs.begin(), zhs.end());
	zhs.erase(unique(zhs.begin(), zhs.end()), zhs.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();
		int y = lower_bound(zhs.begin(), zhs.end(), s[i] + t[i]) - zhs.begin();
		T.add(x, y);
	};
	
	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();
		int l = lower_bound(zhs.begin(), zhs.end(), z[i]) - zhs.begin();
		res[i] = T.get(k, l);
	}
	
	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: 57 / 57