Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <math.h>
- #include <iostream>
- #include <string>
- #include <vector>
- #include <set>
- #include <map>
- #include <cmath>
- #include <deque>
- #include <queue>
- #include <algorithm>
- #include <iterator>
- #include <bitset>
- #include <iomanip>
- #include <functional>
- #include <list>
- #include <cctype>
- #include <ctime>
- #include <stack>
- using namespace std;
- #define int int64_t
- struct Segment {
- int start;
- int end;
- int id;
- };
- signed main() {
- int n;
- cin >> n;
- vector<Segment> s(n);
- for (int i = 0; i < n; i++) {
- cin >> s[i].start >> s[i].end;
- s[i].id = i;
- }
- int q;
- cin >> q;
- vector<int> d(q);
- for (int i = 0; i < q; i++) {
- cin >> d[i];
- }
- stack<Segment> r;
- vector<int> ans(d.size(),-1);
- vector<int> used(d.size(), 1);
- for (int i = 0; i < s.size(); i++) {
- if (r.empty() || (r.top().start <= s[i].start && r.top().end >= s[i].end)) {
- r.push(s[i]);
- }
- else {
- while (!(r.empty()) && !(r.top().start <= s[i].start && r.top().end >= s[i].end)) {
- int start = r.top().start;
- int end = r.top().end;
- int id = r.top().id;
- int left = 0, right = d.size(), mid;
- while (right - left > 1) {
- mid = (left + right) / 2;
- if (d[mid] > start) {
- right = mid;
- }
- else if (d[mid] < start) {
- left = mid;
- }
- else {
- break;
- }
- }
- int f;
- if (d[mid] == start) {
- f = mid;
- }
- else if (abs(d[left] - start) < abs(d[right] - start) && d[left] >= start) {
- f = left;
- }
- else {
- f = right;
- }
- while (f > 0 && d[f] == d[f - 1]) {
- f--;
- }
- while (d[f] <= end) {
- if (used[f] != -1) {
- ans[f] = id + 1;
- used[f] = -1;
- }
- f++;
- }
- r.pop();
- }
- r.push(s[i]);
- }
- }
- while (!r.empty()) {
- int start = r.top().start;
- int end = r.top().end;
- int id = r.top().id;
- int left = 0, right = d.size(), mid;
- while (right - left > 1) {
- mid = (left + right) / 2;
- if (d[mid] > start) {
- right = mid;
- }
- else if (d[mid] < start) {
- left = mid;
- }
- else {
- break;
- }
- }
- int f;
- if (d[mid] == start) {
- f = mid;
- } else if (abs(d[left] - start) < abs(d[right] - start) && d[left] >= start) {
- f = left;
- }
- else {
- f = right;
- }
- while (f > 0 && d[f] == d[f - 1]) {
- f--;
- }
- while (f < d.size() && d[f] <= end) {
- if (used[f] != -1) {
- ans[f] = id + 1;
- used[f] = -1;
- }
- f++;
- }
- r.pop();
- }
- for (int i = 0; i < ans.size(); i++) {
- cout << ans[i] << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement