Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define pb push_back
- #define vi vector<int>
- #define sz(a) (int((a).size()))
- #define mp make_pair
- #define f first
- #define s second
- #define pii pair<int, int>
- using namespace std;
- const int N = 100100;
- int n, m;
- pii a[N];
- vi vals, q;
- struct event {
- int type;
- int len, id;
- event() {}
- event(int _type, int _len, int _id) {
- type = _type;
- len = _len;
- id = _id;
- }
- bool operator < (event other) {
- return type < other.type;
- }
- };
- vector<event> events[N + N + N];
- map<int, int> id;
- int ans[N];
- set<pii> lens;
- int main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- cin >> n;
- for (int i = 1; i <= n; i++) {
- int l, r;
- cin >> l >> r;
- r++;
- a[i] = mp(l, r);
- vals.pb(l);
- vals.pb(r);
- }
- cin >> m;
- for (int i = 1; i <= m; i++) {
- int x;
- cin >> x;
- vals.pb(x);
- q.pb(x);
- }
- sort(vals.begin(), vals.end());
- vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
- for (int i = 0; i < sz(vals); i++) {
- id[vals[i]] = i + 1;
- }
- for (int i = 1; i <= n; i++) {
- int l = a[i].f, r = a[i].s;
- int len = r - l;
- l = id[l], r = id[r];
- events[l].pb(event(0, len, i));
- events[r].pb(event(1, len, i));
- }
- for (int i = 0; i < sz(q); i++) {
- int x = q[i];
- x = id[x];
- events[x].pb(event(2, 0, i + 1));
- }
- for (int i = 1; i <= sz(vals); i++) {
- sort(events[i].begin(), events[i].end());
- }
- for (int i = 1; i <= sz(vals); i++) {
- for (int j = 0; j < sz(events[i]); j++) {
- int len = events[i][j].len, type = events[i][j].type, id = events[i][j].id;
- if (type == 0) {
- lens.insert(mp(len, id));
- } else if (type == 1) {
- lens.erase(mp(len, id));
- } else {
- if (lens.empty()) ans[id] = -1;
- else ans[id] = (*lens.begin()).s;
- }
- }
- }
- for (int i = 1; i <= m; i++) {
- cout << ans[i] << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement