제출 #131752

#제출 시각아이디문제언어결과실행 시간메모리
131752MrTEKExamination (JOI19_examination)C++14
100 / 100
1874 ms97276 KiB
#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];

int query(int x,int val) {
	int answer = 0;
	for ( ; x <= N ; x += (x & -x))
		answer += seg[x].order_of_key({-val,inf});
	return answer;
}

void update(int x,int val) {
	for ( ; x > 0 ; x -= (x & -x))
		seg[x].insert({-val,++tim});
}

int main() {
	// freopen("04-01.txt","r",stdin);
	// freopen("04-01o2.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	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(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";
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...