제출 #624706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
624706		QwertyPi	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	540 ms	257744 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 100013;
int l[N], r[N];
int n, k;
 
struct SegTree{
	int tmin[N * 4] = {0}, tmax[N * 4] = {0};
	void build(int i = 0, int il = 0, int ir = n){
		if(ir - il == 1){
			tmin[i] = tmax[i] = il;
			return;
		}
		int mid = (il + ir) / 2;
		build(i * 2 + 1, il, mid);
		build(i * 2 + 2, mid, ir);
		tmin[i] = INT32_MAX;
		tmax[i] = INT32_MIN;
	}
	void upd_min(int l, int r, int v, int i = 0, int il = 0, int ir = n){
		if(r <= il || ir <= l)
			return;
		if(l <= il && ir <= r){
			tmin[i] = min(tmin[i], v);
			return;
		}
		tmin[i * 2 + 1] = min(tmin[i * 2 + 1], tmin[i]);
		tmin[i * 2 + 2] = min(tmin[i * 2 + 2], tmin[i]);
		int mid = (il + ir) / 2;
		upd_min(l, r, v, i * 2 + 1, il, mid);
		upd_min(l, r, v, i * 2 + 2, mid, ir);
	}
	void upd_max(int l, int r, int v, int i = 0, int il = 0, int ir = n){
		if(r <= il || ir <= l)
			return;
		if(l <= il && ir <= r){
			tmax[i] = max(tmax[i], v);
			return;
		}
		tmax[i * 2 + 1] = max(tmax[i * 2 + 1], tmax[i]);
		tmax[i * 2 + 2] = max(tmax[i * 2 + 2], tmax[i]);
		int mid = (il + ir) / 2;
		upd_max(l, r, v, i * 2 + 1, il, mid);
		upd_max(l, r, v, i * 2 + 2, mid, ir);
	}
	int qry_min(int idx, int i = 0, int il = 0, int ir = n){
		if(il + 1 == ir){
			return tmin[i];
		}
		tmin[i * 2 + 1] = min(tmin[i * 2 + 1], tmin[i]);
		tmin[i * 2 + 2] = min(tmin[i * 2 + 2], tmin[i]);
		int mid = (il + ir) / 2;
		if(idx >= mid){
			return qry_min(idx, i * 2 + 2, mid, ir);
		}else{
			return qry_min(idx, i * 2 + 1, il, mid);
		}
	}
	int qry_max(int idx, int i = 0, int il = 0, int ir = n){
		if(il + 1 == ir){
			return tmax[i];
		}
		tmax[i * 2 + 1] = max(tmax[i * 2 + 1], tmax[i]);
		tmax[i * 2 + 2] = max(tmax[i * 2 + 2], tmax[i]);
		int mid = (il + ir) / 2;
		if(idx >= mid){
			return qry_max(idx, i * 2 + 2, mid, ir);
		}else{
			return qry_max(idx, i * 2 + 1, il, mid);
		}
	}
};
 
struct SparseTable{
	int stl[20][N] = {0}, str[20][N] = {0};
	void build(int l[N], int r[N]){
		for(int i = 0; i < n; i++){
			stl[0][i] = l[i];
			str[0][i] = r[i];
		}
		for(int j = 1; j < 20; j++){
			for(int i = 0; i <= n - (1 << j); i++){
				stl[j][i] = min(stl[j - 1][i], stl[j - 1][i + (1 << j - 1)]);
				str[j][i] = max(str[j - 1][i], str[j - 1][i + (1 << j - 1)]);
			}
		}
	}
	int qry_l(int l, int r){
		int d = __lg(r - l + 1);
		return min(stl[d][l], stl[d][r - (1 << d) + 1]);
	}
	
	int qry_r(int l, int r){
		int d = __lg(r - l + 1);
		return max(str[d][l], str[d][r - (1 << d) + 1]);
	}
} st[20];
 
struct SparseTable2{
	int stl[20][N] = {0}, str[20][N] = {0};
	void build(int l[N], int r[N]){
		for(int i = 0; i < n; i++){
			stl[0][i] = l[i];
			str[0][i] = r[i];
		}
		for(int j = 1; j < 20; j++){
			st[j - 1].build(stl[j - 1], str[j - 1]);
			for(int i = 0; i < n; i++){
				stl[j][i] = st[j - 1].qry_l(stl[j - 1][i], str[j - 1][i]);
				str[j][i] = st[j - 1].qry_r(stl[j - 1][i], str[j - 1][i]);
			}
		}
	}
	int qry_l(int from, int to){
		if(stl[18][from] > to) return -1;
		int ret = 0;
		int l = from, r = from;
		for(int j = 18; j >= 0; j--){
			if(st[j].qry_l(l, r) > to){
				ret += (1 << j);
				int nl = st[j].qry_l(l, r);
				int nr = st[j].qry_r(l, r);
				l = nl, r = nr;
			}
		}
		return ret + 1;
	}
	int qry_r(int from, int to){
		if(str[18][from] < to) return -1;
		int ret = 0;
		int l = from, r = from;
		for(int j = 18; j >= 0; j--){
			if(st[j].qry_r(l, r) < to){
				ret += (1 << j);
				int nl = st[j].qry_l(l, r);
				int nr = st[j].qry_r(l, r);
				l = nl, r = nr;
			}
		}
		return ret + 1;
	}
} st2;
 
int main(){
	cin >> n >> k;
	int m;
	cin >> m;
	SegTree segtree;
	segtree.build();
	for(int i = 0; i < n; i++){
		l[i] = segtree.qry_min(i);
		r[i] = segtree.qry_max(i);
	}
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		if(a < b){
			segtree.upd_max(a, min(b - 1, a + k - 1) + 1, b);
		}else{
			segtree.upd_min(max(b + 1, a - k + 1), a + 1, b);
		}
	}
	
	for(int i = 0; i < n; i++){
		l[i] = segtree.qry_min(i);
		r[i] = segtree.qry_max(i);
	}
	
	st2.build(l, r);
	
	int q;
	cin >> q;
	for(int i = 0; i < q; i++){
		int s, t;
		cin >> s >> t;
		s--; t--;
		if(s < t){
			cout << st2.qry_r(s, t) << endl;
		}else{
			cout << st2.qry_l(s, t) << endl;
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In member function 'void SparseTable::build(int*, int*)':
Main.cpp:85:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   85 |     stl[j][i] = min(stl[j - 1][i], stl[j - 1][i + (1 << j - 1)]);
      |                                                         ~~^~~
Main.cpp:86:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   86 |     str[j][i] = max(str[j - 1][i], str[j - 1][i + (1 << j - 1)]);
      |                                                         ~~^~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13