Submission #1225861

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;

const int INF = ~0U>>1;
const int maxn = 1E5 + 10;

struct d1{
	int l,r,Num; d1(){}
	d1(int l,int r,int Num): l(l),r(r),Num(Num){}
	bool operator < (const d1 &B) const {return l > B.l;}
};

struct d2{
	int l,r,Num; d2(){}
	d2(int l,int r,int Num): l(l),r(r),Num(Num){}
	bool operator < (const d2 &B) const {return r < B.r;}
};

int n,q,N,A[maxn],B[maxn],C[maxn],D[maxn],E[maxn],Ans[maxn],s[maxn];
bool vis[maxn];

vector <pair<int,int> > L[maxn],R[maxn];
priority_queue <d1> Q1;
priority_queue <d2> Q2;

void Calc()
{
	for (int i = 1; i <= n; i++)
		for (int j = A[i]; j <= N; j += j&-j) ++s[j];
	for (int i = 1; i <= n + 1; i++)
		for (int j = C[i]; j <= N; j += j&-j) --s[j];
	int Cnt = 0;
	for (int i = N; i > 0; i--)
	{
		int sum = 0;
		for (int j = 0; j < R[i].size(); j++)
			Q1.push(d1(R[i][j].first,i,R[i][j].second));
		for (int j = i; j > 0; j -= j&-j) sum += s[j];
		if (sum >= -1) continue; sum = -sum - 1;
		for (int l = 0; l < sum; l++)
		{
			d1 k = Q1.top(); Q1.pop();
			++Cnt; vis[k.Num] = 1;
			for (int j = k.l; j <= N; j += j&-j) ++s[j];
			for (int j = k.r + 1; j <= N; j += j&-j) --s[j];
		}
	}
	Ans[0] = Cnt;
	for (int i = 1; i <= N; i++)
	{
		int sum = 0;
		for (int j = 0; j < L[i].size(); j++)
			if (!vis[L[i][j].second]) Q2.push(d2(i,L[i][j].first,L[i][j].second));
		for (int j = i; j > 0; j -= j&-j) sum += s[j];
		if (sum >= 0) {Ans[i] = Cnt; continue;} sum = -sum;
		bool pass = 1;
		for (int l = 0; l < sum; l++)
		{
			if (Q2.empty()) {pass = 0; break;}
			d2 k = Q2.top(); Q2.pop(); ++Cnt;
			if (k.r < i) {pass = 0; break;}
			for (int j = k.l; j <= N; j += j&-j) ++s[j];
			for (int j = k.r + 1; j <= N; j += j&-j) --s[j];
		}
		if (!pass)
		{
			for (int j = i; j <= N; j++) Ans[j] = INF;
			break;
		}
		Ans[i] = Cnt;
	}
}

void Pre_Work()
{
	for (int i = 1; i <= n; i++)
	{
		A[i] = lower_bound(D + 1,D + N + 1,A[i]) - D;
		B[i] = lower_bound(D + 1,D + N + 1,B[i]) - D;
		E[i] = min(A[i],B[i]);
		if (B[i] < A[i])
		{
			L[B[i]].push_back(make_pair(A[i] - 1,i));
			R[A[i] - 1].push_back(make_pair(B[i],i));
		}
	}
	for (int i = 1; i <= n + 1; i++)
		C[i] = lower_bound(D + 1,D + N + 1,C[i]) - D;
	sort(C + 1,C + n + 2); sort(E + 1,E + n + 1);
	int now = 1;
	for (int i = 1; i <= n; i++)
	{
		while (now <= n + 1 && C[now] < E[i]) ++now;
		if (now == n + 2)
		{
			while (q--) puts("-1");
			exit(0);
		}
		++now;
	}
}

int main()
{
	#ifdef DMC
		freopen("DMC.txt","r",stdin);
	#endif
	
	cin >> n;
	for (int i = 1; i <= n; i++) scanf("%d%d",&A[i],&B[i]);
	for (int i = 1; i <= n + 1; i++) scanf("%d",&C[i]),D[i] = C[i];
	cin >> q; sort(D + 1,D + n + 2); N = 1;
	for (int i = 2; i <= n + 1; i++)
		if (D[i] != D[i - 1]) D[++N] = D[i];
	D[++N] = INF; Pre_Work(); Calc();
	while (q--)
	{
		int X,Y; scanf("%d%d",&X,&Y);
		X = lower_bound(D + 1,D + N + 1,X) - D;
		Y = lower_bound(D + 1,D + N + 1,Y) - D;
		int now = max(n + 1 - Ans[X - 1],n - Ans[Y - 1]);
		printf("%d\n",now < 0 ? -1 : now);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:121:56: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d%d",&A[i],&B[i]);
                                                        ^
./Main.cpp:122:64: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n + 1; i++) scanf("%d",&C[i]),D[i] = C[i];
                                                                ^
./Main.cpp:129:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int X,Y; scanf("%d%d",&X,&Y);
                               ^

Judge Result