#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 13;
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;
}
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;
}
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]);
}
};
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++){
SparseTable st;
st.build(stl[j - 1], str[j - 1]);
for(int i = 0; i < n; i++){
stl[j][i] = st.qry_l(stl[j - 1][i], str[j - 1][i]);
str[j][i] = st.qry_r(stl[j - 1][i], str[j - 1][i]);
}
}
}
int qry_l(int from, int to){
if(stl[19][from] > to) return -1;
int ret = 0;
for(int j = 19; j >= 0; j--){
if(stl[j][from] > to)
ret += (1 << j);
}
return ret + 1;
}
int qry_r(int from, int to){
if(str[19][from] < to) return -1;
int ret = 0;
for(int j = 19; j >= 0; j--){
if(str[j][from] < to)
ret += (1 << j);
}
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;
}
}
}
Compilation message
Main.cpp: In member function 'void SparseTable::build(int*, int*)':
Main.cpp:81:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
81 | stl[j][i] = min(stl[j - 1][i], stl[j - 1][i + (1 << j - 1)]);
| ~~^~~
Main.cpp:82:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
82 | str[j][i] = max(str[j - 1][i], str[j - 1][i + (1 << j - 1)]);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
452 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
