제출 #131624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131624		MrTEK	Examination (JOI19_examination)	C++14	2 / 100	3054 ms	206176 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 = 1e9;

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) {
	seg[ind].insert({-val,++tim});
	if (l == r)
		return;
	int mid = (l + r) / 2;
	if (mid >= w)
	update(ind + ind,l,mid,w,val);
	if (mid + 1 <= w)
	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 >= lw && r <= rw) {
		answer += seg[ind].order_of_key({-val,inf});
		return;
	}
	int mid = (l + r) / 2;
	if(mid >= lw) query(ind + ind,l,mid,lw,rw,val);
	if(mid+1<=rw) 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() {
	// freopen("04-01.txt","r",stdin);
	// freopen("04-01o2.txt","w",stdout);
	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;
	sort(queries.begin(),queries.end());
	reverse(queries.begin(),queries.end());
	for (auto i : queries) {
		if (i.first.second == inf)
			update(1,1,n + q,id[i.second.first],i.second.second);
		else
			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: 2 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57