2023年中国传媒大学程序设计大赛 G.跳台滑雪 线段树

传送门

#include <iostream>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <queue>
#include <numeric>
#include <cassert>
#include <bitset>
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <tuple>
 
#define int long long 
#define all(a) a.begin(), a.end()
#define cnt0(x) __builtin_ctz(x)
#define endl '\n'
#define itn int
#define ll long long
#define ull unsigned long long
#define rep(i, a, b) for(int i = a;i <= b; i ++)
#define per(i, a, b) for(int i = a;i >= b; i --)
#define cntone(x) __builtin_popcount(x)
#define db double
// #define fs first
// #define se second
#define AC main(void)
#define HYS std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
typedef std::pair<int, int > PII;
typedef std::pair<int, std::pair<int, int>> PIII;
typedef std::pair<ll, ll> Pll;
typedef std::pair<double, double> PDD;
typedef std::pair<double, int> PDI;
using ld = double long;
const long double eps = 1e-9;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;


int n , m, _;
int ans = INF;

int d1[] = {0, 0, 1, -1};
int d2[] = {1, -1, 0, 0};

struct node{
	int l, r;
	double x;
	int id, score;
}tr[N << 2];

struct node1{
	int fs;
	double se;
	int id;
	
	friend bool operator < (const node1 x, const node1 y){
		if(x.fs != y.fs)	return x.fs < y.fs;
		if(x.se != y.se)	return x.se < y.se;
		return x.id < y.id;
	};
}a[N];

int score[N];

inline void pushup(int u){
	if(tr[u << 1].x < tr[u << 1 | 1].x){
		tr[u].x = tr[u << 1 | 1].x;
		tr[u].id = tr[u << 1 | 1].id;
		tr[u].score = tr[u << 1 | 1].score;
	}
	else if(tr[u << 1].x > tr[u << 1 | 1].x){
		tr[u].x = tr[u << 1].x;
		tr[u].id = tr[u << 1].id;
		tr[u].score = tr[u << 1].score;
	}	
	else{
		if(tr[u << 1].score > tr[u << 1 | 1].score){
			tr[u].x = tr[u << 1].x;
			tr[u].id = tr[u << 1].id;
			tr[u].score = tr[u << 1].score;
		}	
		else if(tr[u << 1].score < tr[u << 1 | 1].score){
			tr[u].x = tr[u << 1 | 1].x;
			tr[u].id = tr[u << 1 | 1].id;
			tr[u].score = tr[u << 1 | 1].score;
		}	
		else{
			if(tr[u << 1].id < tr[u << 1 | 1].id){
				tr[u].x = tr[u << 1].x;
				tr[u].id = tr[u << 1].id;
				tr[u].score = tr[u << 1].score;
			}	
			else{
				tr[u].x = tr[u << 1 | 1].x;
				tr[u].id = tr[u << 1 | 1].id;
				tr[u].score = tr[u << 1 | 1].score;
			}
		}
	}
}

inline void build_tree(int u, int l, int r){
	tr[u] = {l, r};
	if(l == r){
		tr[u].x = a[l].se;
		tr[u].id = a[l].id;
		tr[u].score = a[l].fs;
		return ;
	}
	
	int mid = l + r >> 1;
	build_tree(u << 1, l, mid);
	build_tree(u << 1 | 1, mid + 1, r);
	
	pushup(u);
}

inline void pushup(node &a, node b){
	if(a.x > b.x)	return ;
	if(a.x < b.x)	a = b;
	else{
		if(a.score > b.score)	return ;
		if(a.score < b.score)	a = b;
		else{
			if(a.id < b.id)	return ;
			a = b;
		}
	}
}

inline node query(int u, int l, int r){
	if(tr[u].l >= l && tr[u].r <= r)	return tr[u];
	
	int mid = tr[u].l + tr[u].r >> 1;
	node ans;
	ans.id = INF;
	ans.x = 0.0;
	ans.score = 0ll;
	if(l <= mid){
		node tmp = query(u << 1, l, r);
		pushup(ans, tmp);
	}	
	if(r > mid){
		node tmp = query(u << 1 | 1, l, r);
		pushup(ans, tmp);
	}	
	
	return ans;
}

int g[N];

inline void solve(){
	int k;
	std::cin >> n >> m >> k;
	double mx = 0;
	int pos = INF;
	int sc = 0;
	int mxs = 0;
	for(int i = 1; i <= n; i ++){
		std::cin >> a[i].se >> a[i].fs;
		a[i].id = i - 1;
		if(a[i].se > mx){
			mx = a[i].se;
			pos = i - 1;
			sc = a[i].fs;
		}else if(a[i].se == mx){
			if(a[i].fs > sc){
				mx = a[i].se;
				pos = i - 1;
				sc = a[i].fs;
			}else if(a[i].fs == sc){
				if(pos < a[i].id)	continue;
				sc = a[i].fs;
				mx = a[i].se;
				pos = i - 1;
			}
		}	
		
		mxs = std::max(mxs, a[i].fs);
	}
	
	std::sort(a + 1, a + n + 1);
	
	for(int i = 1; i <= n; i ++)	g[i] = a[i].fs;
	
	build_tree(1, 1, n);
	
	for(int i = 1; i <= m; i ++)	std::cin >> score[i];
	
	std::sort(score + 1, score + m + 1, std::greater<int>());
	
	while(k --){
		int rk, s;
		std::cin >> s >> rk;
		if(rk > m || score[rk] <= s){
			std::cout << pos << '\n';
			continue;
		}	
		
		int c = score[rk] - s;
		
		
		if(c > mxs){
			std::cout << -1 << '\n';
			continue;
		}
		int position = std::lower_bound(g + 1, g + n + 1, c) - g;
		node ans = query(1, position, n);
		std::cout << ans.id << '\n';
	}
}

signed AC{
   	HYS
   	
	_ = 1;
   	//std::cin >> _;
	while(_ --)
    	solve();

    return 0;
}