Submission #131445

#	Time	Username	Problem	Language	Result	Execution time	Memory
131445		MrTEK	Examination (JOI19_examination)	C++14	0 / 100	3062 ms	203576 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

using namespace __gnu_pbds;
using ordered_set = tree<ii, null_type,less<ii>, rb_tree_tag,tree_order_statistics_node_update>;

const int N = 2e5 + 5;
const int inf = 2e9 + 500;

vector <int> v;
vector <pair<ii,ii>> queries;
map <int,int> id;
int answer,n,q,s[N],t[N],x[N],y[N],z[N],ans[N],tim;
ordered_set seg[N << 2];

void update(int ind,int l,int r,int w,int val) {
	if (l > w || r < w)
		return;
	seg[ind].insert({-val,++tim});
	if (l == r)
		return;
	int mid = (l + r) / 2;
	update(ind + ind,l,mid,w,val);
	update(ind + ind + 1,mid + 1,r,w,val);
}

void query(int ind,int l,int r,int lw,int rw,int val) {
	if (l > rw || r < lw)
		return;
	if (l >= lw && r <= rw) {
		answer += seg[ind].order_of_key({-val,-inf});
		return;
	}
	int mid = (l + r) / 2;
	query(ind + ind,l,mid,lw,rw,val);
	query(ind + ind + 1,mid + 1,r,lw,rw,val);
}

int query(int x,int val) {
	answer = 0;
	query(1,1,n + q,x,n + q,val);
	return answer;
}

int main() {
	cin >> n >> q;
	for (int i = 1 ; i <= n ; i++) {
		cin >> s[i] >> t[i];
		v.push_back(t[i]);
		queries.push_back({{s[i],inf},{t[i],s[i] + t[i]}});
	}
	for (int i = 1 ; i <= q ; i++) {
		cin >> x[i] >> y[i] >> z[i];
		v.push_back(y[i]);
		queries.push_back({{x[i],i},{y[i],z[i]}});
	}
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end()) - v.begin());
	int dsa = 0;
	for (auto i : v) {
		id[i] = ++dsa;
		// cerr << dsa << ". " << i << endl;
	}
	sort(queries.begin(),queries.end());
	reverse(queries.begin(),queries.end());
	for (auto i : queries) {
		if (i.first.second == inf) {
			// cerr << "update -> " << i.second.first << " " << i.second.second << endl;
			update(1,1,n + q,id[i.second.first],i.second.second);
		}
		else {
			// cerr << "query -> " << i.second.first << " " << i.second.second << endl;
			ans[i.first.second] = query(id[i.second.first],i.second.second);
		}
	}
	for (int i = 1 ; i <= q ; i++)
		cout << ans[i] << "\n";
}

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