제출 #666796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
666796		Koful123	Examination (JOI19_examination)	C++17	0 / 100	3071 ms	30656 KiB

examination

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ms multiset<pair<int,int>>

struct node{
	multiset<pair<int,int>> s;
	node operator + (node other){
		node res; ms tmp = s;
		for(auto[x,y] : other.s){
			if(x == 0) continue;
			tmp.insert({x,y});
		}
		int cur = 0;
		for(auto[x,y] : tmp){
			res.s.insert({x,cur}); cur++;
		}
		return res;
	};
};

struct SegTree{
	int n; vector<node> seg;
	SegTree(int _n){
		seg.resize(4 * (n = _n) + 4);
		for(node &x : seg){
			x.s.insert({0,0});
		}
	};
	void upd(int v,int tl,int tr,int pos,int x){
		if(tl > pos || tr < pos) return;
		if(tl == pos && tr == pos){
			auto it = seg[v].s.upper_bound({x,0}); it--;
			seg[v].s.insert({x,it -> ss + 1}); 
			return;
		}
		int tm = (tl + tr) / 2;
		upd(v*2,tl,tm,pos,x),upd(v*2+1,tm+1,tr,pos,x);
		seg[v] = seg[v*2] + seg[v*2+1];
	}
	void upd(int pos,int x){
		upd(1,1,n,pos,x);
	}
	int get(int v,int tl,int tr,int l,int r,int x){
		if(tl > r || tr < l) return 0;
		if(tl >= l && tr <= r){
			return seg[v].s.size() - prev(seg[v].s.lower_bound({x,0})) -> ss - 1;
		}
		int tm = (tl + tr) / 2;
		return get(v*2,tl,tm,l,r,x) + get(v*2+1,tm+1,tr,l,r,x);
	}
	int get(int pos,int x){
		return get(1,1,n,pos,n,x);
	}
};

void solve(){

	int n,t;
	cin >> n >> t;

	vector<int> nums,ans(t + 1); vector<pair<int,int>> v(n);
	for(auto &[x,y] : v){
		cin >> x >> y;
		nums.pb(y);
	} 

	vector<array<int,4>> q(t); int pos = 0;
	for(auto &[x,y,z,t] : q){
		cin >> x >> y >> z; t = ++pos;
	}

	auto f = [&](int x){
		return lower_bound(all(nums),x) - nums.begin() + 1;
	};

	sort(all(nums)), sort(rall(v)), sort(rall(q));
	nums.resize(unique(all(nums)) - nums.begin());

	pos = -1; SegTree seg(nums.size());
	for(auto[x,y,z,t] : q){
		while(pos + 1 < n && v[pos+1].ff >= x){
			++pos; seg.upd(f(v[pos].ss),v[pos].ss + v[pos].ff); 
		}
		ans[t] = seg.get(f(y),z); 
	}

	for(int i = 1; i <= t; i++){
		cout << ans[i] << endl;
	}
}
 
signed main(){	
 		
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int t = 1;
//	cin >> t;
 
	while(t--)
		solve();
 
	return 0;
}

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