Submission #613445

#	Time	Username	Problem	Language	Result	Execution time	Memory
613445		amunduzbaev	Examination (JOI19_examination)	C++17	22 / 100	3003 ms	436332 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 ST2{
	ST tree[N << 2];
	void add(int i, int v, int lx = 0, int rx = N, int x = 1){
		tree[x].add(v, 1);
		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].get(v, N);
		} 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, 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: 0 / 21
• Subtask 4: 0 / 57