Submission #69481778

---

Source Code Expand

/* Code By WCM */
/*
Date:
大致思路：
复杂度：
期望得分：
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <vector>
#include <queue>
#define pii pair<int,int>
#define F first
#define S second

using namespace std;

inline int read();
void write(int);
void writeln(int);

const int N = 1e6 + 5, inf = 1e9;
int n, Q, minn[N << 2], maxx[N << 2];

#define lson (u << 1)
#define rson (u << 1 | 1)
void pushup(int u) {
	minn[u] = min(minn[lson], minn[rson]), maxx[u] = max(maxx[lson], maxx[rson]);
}
void build(int u, int l, int r) {
	if(l == r) { minn[u] = inf, maxx[u] = 0; return ; }
	int mid = l + r >> 1;
	build(lson, l, mid), build(rson, mid + 1, r);
	pushup(u);
}
void update(int u, int l, int r, int p, int v) {
	if(l == r) { minn[u] = maxx[u] = v; return ; }
	int mid = l + r >> 1;
	if(p <= mid) update(lson, l, mid, p, v);
	else update(rson, mid + 1, r, p, v);
	pushup(u);
}
pii query(int u, int l, int r, int ql, int qr) {
	if(ql > r || qr < l) return {inf, 0};
	if(ql <= l && r <= qr) return {minn[u], maxx[u]};
	int mid = l + r >> 1;
	pii L = query(lson, l, mid, ql, qr), R = query(rson, mid + 1, r, ql, qr);
	return {min(L.F, R.F), max(L.S, R.S)};
}

int main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	n = read(), Q = read();
	build(1, 1, n);
	while(Q--) {
		int a = read(), b = read();
		if(a > b) swap(a, b);
		int l = a + 1, r = b - 1;
		if(l > r) puts("Yes"), update(1, 1, n, a, b), update(1, 1, n, b, a);
		else {
			pii res = query(1, 1, n, l, r);
			int mv = res.F, mx = res.S;
			if(mv == inf && mx == 0) puts("Yes"), update(1, 1, n, a, b), update(1, 1, n, b, a);
			else {
				if(mv < a || mx > b) puts("No");
				else puts("Yes"), update(1, 1, n, a, b), update(1, 1, n, b, a);
			}
		}
	}
	
//	printf("\nThe time used: ");
//	printf("%.2lfs",(double)clock()/CLOCKS_PER_SEC);

	return 0;

}

inline int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while( !(ch >= '0' && ch <= '9') ) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		res = (res << 1) + (res << 3) + (ch ^ 48);
		ch = getchar();
	}
	return res * f;
}

void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10;
		x /= 10;
	} while(x);
	while(top) putchar(sta[--top] ^ 48);
}

void writeln(int x) {
	write(x);
	putchar('\n');
}

Submission Info

Compile Error

Main.cpp: In function ‘void build(int, int, int)’:
Main.cpp:36:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   36 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function ‘void update(int, int, int, int, int)’:
Main.cpp:42:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   42 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function ‘std::pair<int, int> query(int, int, int, int, int)’:
Main.cpp:50:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   50 |         int mid = l + r >> 1;
      |                   ~~^~~

Judge Result