Submission #1230012

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define dep(i,a,b) for(int i = a; i >= b; i--) 
#define Rep(i,a) for(int i = 0; i < a; i++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ab(x) ((x) < 0 ? -(x) : (x))
using namespace std;
typedef long long LL;
typedef map<int, int>::iterator mit;
typedef set<int>::iterator sit;
typedef pair<int, int> pii;
#define x first
#define y second
const int N = 1e5 + 10, inf = 5e6 + 10;
bool haveans = true;
int n, c[N], d[N]; pii a[N];
bool side[N];
priority_queue<pii> q;
vector<pii> nd[N];

void init() {
	rep(i,1,n) 
		a[i].x = lower_bound(c + 1, c + (n + 1) + 1, a[i].x) - c,
		a[i].y = lower_bound(c + 1, c + (n + 1) + 1, a[i].y) - c;
}

int C[N];
int main() {
	scanf("%d",&n);
	rep(i,1,n) scanf("%d%d",&a[i].x,&a[i].y);
	rep(i,1,n + 1) scanf("%d",c + i);
	sort(c + 1, c + (n + 1) + 1);
	init();
	
	memset(side, true, sizeof(side));
	rep(i,1,n + 1) d[i] = 0;
	rep(i,1,n) d[a[i].x - 1]--;
	rep(i,1,n) nd[a[i].x - 1].pb(mp(-a[i].y, i));

	int delta = 0; d[n + 2] = n;
	dep(i,n + 1,1) {
		int len = nd[i].size(); Rep(j,len) q.push(nd[i][j]);
		d[i] += d[i + 1]; C[i] = d[i] - i;
		while (C[i] < -1) {
			if (q.empty() || -q.top().x > i) { haveans = false; break; }
			else {
				pii t = q.top(); q.pop(); side[t.y] = false;
				delta++, d[i]++, C[i]++, d[-t.x - 1]--;
			}
		}
	}
	
	rep(i,0,n + 1) d[i] = 0;
	rep(i,1,n) d[side[i] ? a[i].x : a[i].y]++;
	rep(i,1,n + 1) d[i] += d[i - 1], C[i] = d[i] - i;
	
	while (!q.empty()) q.pop();
	rep(i,1,n + 1) nd[i].clear();
	rep(i,1,n) if (side[i]) nd[a[i].y].pb(mp(a[i].x - 1, i));
	int cur = 0; static int f[N];
	
	rep(i,1,n + 1) {
		int len = nd[i].size(); Rep(j,len) q.push(nd[i][j]);
		f[i] = f[i - 1];
		if (C[i] == -1) {
			if (cur < i) {
				if (q.empty() || q.top().x < i) f[i] = inf;
				else {
					pii t = q.top(); q.pop(); 
					cur = t.x;
					f[i]++;
				}
			}
		}
	}
	
	int q; scanf("%d",&q);
	rep(i,1,q) {
		int a, b; scanf("%d%d",&a,&b);
		a = lower_bound(c + 1, c + (n + 1) + 1, a) - c;
		b = lower_bound(c + 1, c + (n + 1) + 1, b) - c;
		if (!haveans) printf("-1\n");
		else {
			int x = f[a - 1] + delta;
			int y = f[b - 1] + delta;
			int ans = min(x, y + 1);
			if (ans > n + 1) printf("-1\n");
			else printf("%d\n",n + 1 - ans);
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:38:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:39:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i,1,n) scanf("%d%d",&a[i].x,&a[i].y);
                                          ^
./Main.cpp:40:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i,1,n + 1) scanf("%d",c + i);
                                  ^
./Main.cpp:86:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int q; scanf("%d",&q);
                       ^
./Main.cpp:88:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int a, b; sca...

Judge Result