Submission #2116844

---

Source Code Expand

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define SIZE 262144
typedef pair<int, int>pii;
class segtree
{
public:
	int seg[SIZE * 2];
	int flag[SIZE * 2];
	int idx[SIZE * 2];
	void init()
	{
		for (int i = 0; i < SIZE; i++)idx[SIZE + i] = i;
		for (int i = SIZE - 1; i >= 1; i--)idx[i] = idx[i * 2];
	}
	void update(int beg, int end, int node, int lb, int ub, int num)
	{
		if (ub<beg || end<lb)return;
		if (beg <= lb&&ub <= end)
		{
			seg[node] += num;
			flag[node] += num;
			return;
		}
		if (flag[node])
		{
			seg[node * 2] += flag[node];
			seg[node * 2 + 1] += flag[node];
			flag[node * 2] += flag[node];
			flag[node * 2 + 1] += flag[node];
			flag[node] = 0;
		}
		update(beg, end, node * 2, lb, (lb + ub) / 2, num);
		update(beg, end, node * 2 + 1, (lb + ub) / 2 + 1, ub, num);
		seg[node] = min(seg[node * 2], seg[node * 2 + 1]);
		if (seg[node] == seg[node * 2])idx[node] = idx[node * 2];
		else idx[node] = idx[node * 2 + 1];
	}
	pii get(int beg, int end, int node, int lb, int ub)
	{
		if (ub < beg || end < lb)return make_pair(1000000000, -1);
		if (beg <= lb&&ub <= end)
		{
			return make_pair(seg[node], idx[node]);
		}
		if (flag[node])
		{
			seg[node * 2] += flag[node];
			seg[node * 2 + 1] += flag[node];
			flag[node * 2] += flag[node];
			flag[node * 2 + 1] += flag[node];
			flag[node] = 0;
		}
		pii a = get(beg, end, node * 2, lb, (lb + ub) / 2), b = get(beg, end, node * 2 + 1, (lb + ub) / 2 + 1, ub);
		int d;
		if (a.first <= b.first)d = a.second;
		else d = b.second;
		return make_pair(min(a.first, b.first), d);
	}
};
segtree tree;
vector<int>pat[SIZE];
int ans[SIZE];
int main()
{
	int num;
	scanf("%d", &num);
	vector<pii>v;
	for (int i = 0; i < num; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		zb = min(za, zb);
		v.push_back(make_pair(za, zb));
	}
	vector<int>zat;
	for (int i = 0; i < num + 1; i++)
	{
		int z;
		scanf("%d", &z);
		zat.push_back(z);
	}
	sort(zat.begin(), zat.end());
	for (int i = 0; i < num; i++)
	{
		v[i].first = lower_bound(zat.begin(), zat.end(), v[i].first) - zat.begin();
		v[i].second = lower_bound(zat.begin(), zat.end(), v[i].second) - zat.begin();
	}
	sort(v.begin(), v.end());
	tree.init();
	for (int i = 0; i < num + 1; i++)tree.update(i, num, 1, 0, SIZE - 1, -1);
	for (int i = 0; i < num; i++)tree.update(v[i].second, num, 1, 0, SIZE - 1, 1);
	int pt = 0;
	ans[num + 1] = -1;
	int cnt = 0;
	for (int i = 0; i < num; i++)
	{
		//printf("------%d %d\n", v[i].second, v[i].first);
		//for (int j = 0; j < num + 2; j++)printf("%d ", tree.get(j, j, 1, 0, SIZE - 1).first); printf("\n");
		pii r = tree.get(v[i].second, v[i].first - 1, 1, 0, SIZE - 1);
		//printf(" %d %d\n", r.first, r.second);
		if (r.first >= 1)
		{
			tree.update(v[i].second, v[i].first - 1, 1, 0, SIZE - 1, -1);
			cnt++;
		}
		else if (r.first == 0)
		{
			for (int j = pt; j <= r.second; j++)pat[v[i].first].push_back(j);
			pt = max(pt, r.second + 1);
		}
	}
	for (int i = pt; i < num + 1; i++)ans[i] = cnt;
	for (int i = num; i >= 0; i--)for (int j = 0; j < pat[i].size(); j++)ans[pat[i][j]] = ans[i] + 1;
	for (int i = 0; i < num + 1; i++)
	{
		if (tree.get(0, SIZE - 1, 1, 0, SIZE - 1).first <= -2)ans[i] = -1;
		if (tree.get(0, i - 1, 1, 0, SIZE - 1).first <= -1)ans[i] = -1;
	}
	int query;
	scanf("%d", &query);
	for (int i = 0; i < query; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		zb = min(za, zb);
		za = lower_bound(zat.begin(), zat.end(), za) - zat.begin();
		zb = lower_bound(zat.begin(), zat.end(), zb) - zat.begin();
		if (ans[za] == -1)printf("%d\n", ans[zb]);
		else printf("%d\n", max(ans[za] + 1, ans[zb]));
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:69:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &num);
                   ^
./Main.cpp:74:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &za, &zb);
                          ^
./Main.cpp:82:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &z);
                  ^
./Main.cpp:123:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &query);
                     ^
./Main.cpp:127:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &za, &zb);
                          ^

Judge Result