#include <bits/stdc++.h>
namespace IO {
const int DPAIRSIZ = 1 << 10;
char BB[DPAIRSIZ], *SS = BB, *TT = BB;
inline char getcha() {
return SS == TT && (TT = (SS = BB) + fread(BB, 1, DPAIRSIZ, stdin), SS == TT) ? EOF : *SS++;
}
template<typename T = int>
inline T read() {
T x = 0;
int fu = 1;
char c = getcha();
while (c > 57 || c < 48) {
if (c == 45) fu = -1;
c = getcha();
}
while (c <= 57 && c >= 48) {
x = x * 10 + c - 48;
c = getcha();
}
x *= fu;
return x;
}
template<typename T>
inline void read(T &x) {
x = 0;
int fu = 1;
char c = getcha();
while (c > 57 || c < 48) {
if (c == 45) fu = -1;
c = getcha();
}
while (c <= 57 && c >= 48) {
x = x * 10 + c - 48;
c = getcha();
}
x *= fu;
}
template<typename T>
inline void read(T *bg, T *ed) { while (bg != ed) read(*bg++); }
inline void read(char &ch) {
ch = getcha();
while (ch <= 32) ch = getcha();
}
inline void read(char *s) {
char ch = getcha();
while (ch <= 32) ch = getcha();
while (ch > 32) *s++ = ch, ch = getcha();
*s = '\0';
}
inline void read(std::string &s) {
char ch = getcha();
while (ch <= 32) ch = getcha();
while (ch > 32) s.push_back(ch), ch = getcha();
}
inline void sread(char *s) {
char ch = getcha();
while (ch < 32) ch = getcha();
while (ch >= 32) *s++ = ch, ch = getcha();
*s = '\0';
}
inline void pread(char *&s) {
char ch = getcha();
while (ch <= 32) ch = getcha();
while (ch > 32) *s++ = ch, ch = getcha();
*s = '\0';
}
inline void spread(char *&s) {
char ch = getcha();
while (ch < 32) ch = getcha();
while (ch >= 32) *s++ = ch, ch = getcha();
*s = '\0';
}
template<typename T, typename ...Args>
inline void read(T &x, Args &...args) {
read(x);
read(args...);
}
char out[DPAIRSIZ], *Out = out;
#define flush() fwrite(out, 1, Out - out, stdout)
inline void putcha(char x) {
*Out++ = x;
if (Out - out >= (DPAIRSIZ)) flush(), Out = out;
}
template<typename T>
inline void fprint(T x) {
if (x < 0) putcha(45), x = -x;
if (x > 9) fprint(x / 10);
putcha(x % 10 + 48);
}
inline void print() { putcha(10); }
template<typename T>
inline void print(T x) {
fprint(x);
putcha(10);
}
inline void print(char *ch) {
while (*ch != '\0') putcha(*(ch++));
putcha(10);
}
inline void put(char *ch) { while (*ch != '\0') putcha(*(ch++)); }
inline void print(const char *ch) {
while (*ch != '\0') putcha(*(ch++));
putcha(10);
}
inline void put(const char *ch) { while (*ch != '\0') putcha(*(ch++)); }
template<typename T, typename ...Args>
inline void print(T x, Args ...args) {
fprint(x);
putcha(32);
print(args...);
}
template<typename ...Args>
inline void print(const char *ch, Args ...args) {
while (*ch != '\0') putcha(*(ch++));
putcha(32);
print(args...);
}
template<typename ...Args>
inline void print(char *ch, Args ...args) {
while (*ch != '\0') putcha(*(ch++));
putcha(32);
print(args...);
}
template<typename T, typename ...Args>
inline void printl(T x, Args ...args) {
fprint(x);
putcha(10);
printl(args...);
}
template<typename ...Args>
inline void printl(const char *ch, Args ...args) {
while (*ch != '\0') putcha(*(ch++));
putcha(10);
printl(args...);
}
template<typename ...Args>
inline void printl(char *ch, Args ...args) {
while (*ch != '\0') putcha(*(ch++));
putcha(10);
printl(args...);
}
template<typename T>
inline void sprint(T x) {
fprint(x);
putcha(32);
}
template<typename T, typename ...Args>
inline void sprint(T x, Args ...args) {
fprint(x);
putcha(32);
sprint(args...);
}
template<typename T>
inline void sprint(T *bg, T *ed) { while (bg != ed) sprint(*bg++); }
template<typename T>
inline void print(T *bg, T *ed) {
while (bg != ed) sprint(*bg++);
putcha(10);
}
template<typename T>
inline void printl(T *bg, T *ed) { while (bg != ed) print(*bg++); }
class AutoFlush {
public:
~AutoFlush() { flush(); }
} __AutoFlush;
} // namespace IO
using namespace IO;
#define vc vector
#define nd node*
#define pnd pair<nd, nd>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vc<pll> vpll;
typedef vc<vll> vvll;
typedef vc<vpll> vvpll;
template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
ll operator()(const ll a, const ll b) {
return (a * b) % MOD;
}
};
template<typename T>
inline void sort(T &a) {
sort(a.begin(), a.end());
}
template<typename T>
inline void unique(T &a) {
a.resize(unique(a.begin(), a.end()) - a.begin());
}
template<typename T>
inline void reverse(T &a) {
reverse(a.begin(), a.end());
}
const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;
const ll N = 200005;
pair<int, int> t[17][N * 4];
pair<int, int> up[17][N];
void build(int id, int v = 1, int l = 0, int r = N - 1) {
if (l == r) return void(t[id][v] = up[id][l]);
int mid = (l + r) / 2;
build(id, v * 2, l, mid), build(id, v * 2 + 1, mid + 1, r);
t[id][v].first = min(t[id][v * 2].first, t[id][v * 2 + 1].first);
t[id][v].second = max(t[id][v * 2].second, t[id][v * 2 + 1].second);
}
pair<int, int> get(int id, int l_, int r_, int v = 1, int l = 0, int r = N - 1) {
if (l_ <= l && r <= r_) return t[id][v];
if (r < l_ || r_ < l) return {1e9, -1e9};
int mid = (l + r) / 2;
pair<int, int> ans = get(id, l_, r_, v * 2, l, mid);
auto tmp = get(id, l_, r_, v * 2 + 1, mid + 1, r);
ans.first = min(ans.first, tmp.first);
ans.second = max(ans.second, tmp.second);
return ans;
}
int main() {
int n, k;
read(n, k);
int m;
read(m);
vc<pair<int, int>> straight, cursed;
for (int i = 0; i < m; ++i) {
int l, r;
read(l, r);
--l;
--r;
if (l <= r) straight.emplace_back(l, r);
else cursed.emplace_back(l, r);
}
vc<pair<int, int>> go(n);
{// updating for straight
vc<vc<int>> add(n + 1);
vc<vc<int>> del(n + 1);
for (int i = 0; i < straight.size(); ++i) {
int begin = straight[i].first;
int end = min(straight[i].second + 1, straight[i].first + k);
add[begin].push_back(straight[i].second);
del[end].push_back(straight[i].second);
}
for (int i = 0; i < n; ++i) go[i] = {i, i};
multiset<int> e;
for (int i = 0; i < n; ++i) {
for (auto x: del[i]) e.erase(e.find(x));
for (auto x: add[i]) e.insert(x);
if (!e.empty()) go[i].second = max(go[i].second, *e.rbegin());
}
}
{// updating for cursed
vc<vc<int>> add(n + 1);
vc<vc<int>> del(n + 1);
for (int i = 0; i < cursed.size(); ++i) {
int begin = cursed[i].first;
int end = max(cursed[i].second - 1, cursed[i].first - k);
add[begin].push_back(cursed[i].second);
if (end >= 0) del[end].push_back(cursed[i].second);
}
multiset<int> e;
for (int i = n - 1; i >= 0; --i) {
for (auto x: del[i]) e.erase(e.find(x));
for (auto x: add[i]) e.insert(x);
if (!e.empty()) go[i].first = min(go[i].first, *e.begin());
}
}
for (int i = 0; i < n; ++i) {
up[0][i] = go[i];
}
build(0);
for (int sz = 1; sz < 17; ++sz) {
for (int v = 0; v < n; ++v) {
up[sz][v] = get(sz - 1, up[sz - 1][v].first, up[sz - 1][v].second);
}
build(sz);
}
int q;
read(q);
while (q--) {
int v, to;
read(v, to);
--v, --to;
pair<int, int> nw = {v, v};
int ans = 0;
for (int j = 16; j >= 0; --j) {
auto tmp = get(j, nw.first, nw.second);
if (!(tmp.first <= to && to <= tmp.second)) nw = tmp, ans += 1 << j;
}
if (!(nw.first <= to && to <= nw.second)) {
auto tmp = get(0, nw.first, nw.second);
nw = tmp;
++ans;
}
if (nw.first <= to && to <= nw.second) {
cout << ans << '\n';
} else {
cout << -1 << '\n';
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:285:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
285 | for (int i = 0; i < straight.size(); ++i) {
| ~~^~~~~~~~~~~~~~~~~
Main.cpp:302:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
302 | for (int i = 0; i < cursed.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
70348 KB |
Output is correct |
2 |
Correct |
75 ms |
70336 KB |
Output is correct |
3 |
Correct |
67 ms |
70288 KB |
Output is correct |
4 |
Correct |
68 ms |
70348 KB |
Output is correct |
5 |
Correct |
69 ms |
70324 KB |
Output is correct |
6 |
Correct |
70 ms |
70472 KB |
Output is correct |
7 |
Correct |
77 ms |
70360 KB |
Output is correct |
8 |
Correct |
66 ms |
70288 KB |
Output is correct |
9 |
Correct |
70 ms |
70388 KB |
Output is correct |
10 |
Correct |
65 ms |
70308 KB |
Output is correct |
11 |
Correct |
67 ms |
70360 KB |
Output is correct |
12 |
Correct |
70 ms |
70348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
70348 KB |
Output is correct |
2 |
Correct |
75 ms |
70336 KB |
Output is correct |
3 |
Correct |
67 ms |
70288 KB |
Output is correct |
4 |
Correct |
68 ms |
70348 KB |
Output is correct |
5 |
Correct |
69 ms |
70324 KB |
Output is correct |
6 |
Correct |
70 ms |
70472 KB |
Output is correct |
7 |
Correct |
77 ms |
70360 KB |
Output is correct |
8 |
Correct |
66 ms |
70288 KB |
Output is correct |
9 |
Correct |
70 ms |
70388 KB |
Output is correct |
10 |
Correct |
65 ms |
70308 KB |
Output is correct |
11 |
Correct |
67 ms |
70360 KB |
Output is correct |
12 |
Correct |
70 ms |
70348 KB |
Output is correct |
13 |
Correct |
90 ms |
70760 KB |
Output is correct |
14 |
Correct |
87 ms |
70776 KB |
Output is correct |
15 |
Correct |
79 ms |
70776 KB |
Output is correct |
16 |
Correct |
81 ms |
70688 KB |
Output is correct |
17 |
Correct |
78 ms |
70712 KB |
Output is correct |
18 |
Correct |
80 ms |
70728 KB |
Output is correct |
19 |
Correct |
90 ms |
70752 KB |
Output is correct |
20 |
Correct |
74 ms |
70776 KB |
Output is correct |
21 |
Correct |
73 ms |
70872 KB |
Output is correct |
22 |
Correct |
83 ms |
70900 KB |
Output is correct |
23 |
Correct |
80 ms |
70696 KB |
Output is correct |
24 |
Correct |
100 ms |
70676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
496 ms |
93244 KB |
Output is correct |
2 |
Correct |
461 ms |
89112 KB |
Output is correct |
3 |
Correct |
538 ms |
93784 KB |
Output is correct |
4 |
Correct |
462 ms |
89068 KB |
Output is correct |
5 |
Correct |
533 ms |
96544 KB |
Output is correct |
6 |
Correct |
532 ms |
97968 KB |
Output is correct |
7 |
Correct |
365 ms |
99708 KB |
Output is correct |
8 |
Correct |
373 ms |
94188 KB |
Output is correct |
9 |
Correct |
337 ms |
94512 KB |
Output is correct |
10 |
Correct |
544 ms |
90040 KB |
Output is correct |
11 |
Correct |
481 ms |
90608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
639 ms |
89428 KB |
Output is correct |
2 |
Correct |
694 ms |
98404 KB |
Output is correct |
3 |
Correct |
779 ms |
94840 KB |
Output is correct |
4 |
Correct |
515 ms |
101120 KB |
Output is correct |
5 |
Correct |
608 ms |
99384 KB |
Output is correct |
6 |
Correct |
541 ms |
99380 KB |
Output is correct |
7 |
Correct |
767 ms |
91820 KB |
Output is correct |
8 |
Correct |
725 ms |
92928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
934 ms |
94088 KB |
Output is correct |
2 |
Correct |
890 ms |
93276 KB |
Output is correct |
3 |
Correct |
910 ms |
88744 KB |
Output is correct |
4 |
Correct |
772 ms |
86820 KB |
Output is correct |
5 |
Correct |
648 ms |
85716 KB |
Output is correct |
6 |
Correct |
686 ms |
85284 KB |
Output is correct |
7 |
Correct |
679 ms |
95208 KB |
Output is correct |
8 |
Correct |
74 ms |
70368 KB |
Output is correct |
9 |
Correct |
79 ms |
70752 KB |
Output is correct |
10 |
Correct |
642 ms |
96304 KB |
Output is correct |
11 |
Correct |
730 ms |
98456 KB |
Output is correct |
12 |
Correct |
785 ms |
96512 KB |
Output is correct |
13 |
Correct |
767 ms |
98440 KB |
Output is correct |
14 |
Correct |
70 ms |
70348 KB |
Output is correct |
15 |
Correct |
79 ms |
70692 KB |
Output is correct |
16 |
Correct |
556 ms |
93972 KB |
Output is correct |
17 |
Correct |
908 ms |
94896 KB |
Output is correct |
18 |
Correct |
823 ms |
94852 KB |
Output is correct |
19 |
Correct |
776 ms |
94680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
70348 KB |
Output is correct |
2 |
Correct |
75 ms |
70336 KB |
Output is correct |
3 |
Correct |
67 ms |
70288 KB |
Output is correct |
4 |
Correct |
68 ms |
70348 KB |
Output is correct |
5 |
Correct |
69 ms |
70324 KB |
Output is correct |
6 |
Correct |
70 ms |
70472 KB |
Output is correct |
7 |
Correct |
77 ms |
70360 KB |
Output is correct |
8 |
Correct |
66 ms |
70288 KB |
Output is correct |
9 |
Correct |
70 ms |
70388 KB |
Output is correct |
10 |
Correct |
65 ms |
70308 KB |
Output is correct |
11 |
Correct |
67 ms |
70360 KB |
Output is correct |
12 |
Correct |
70 ms |
70348 KB |
Output is correct |
13 |
Correct |
90 ms |
70760 KB |
Output is correct |
14 |
Correct |
87 ms |
70776 KB |
Output is correct |
15 |
Correct |
79 ms |
70776 KB |
Output is correct |
16 |
Correct |
81 ms |
70688 KB |
Output is correct |
17 |
Correct |
78 ms |
70712 KB |
Output is correct |
18 |
Correct |
80 ms |
70728 KB |
Output is correct |
19 |
Correct |
90 ms |
70752 KB |
Output is correct |
20 |
Correct |
74 ms |
70776 KB |
Output is correct |
21 |
Correct |
73 ms |
70872 KB |
Output is correct |
22 |
Correct |
83 ms |
70900 KB |
Output is correct |
23 |
Correct |
80 ms |
70696 KB |
Output is correct |
24 |
Correct |
100 ms |
70676 KB |
Output is correct |
25 |
Correct |
496 ms |
93244 KB |
Output is correct |
26 |
Correct |
461 ms |
89112 KB |
Output is correct |
27 |
Correct |
538 ms |
93784 KB |
Output is correct |
28 |
Correct |
462 ms |
89068 KB |
Output is correct |
29 |
Correct |
533 ms |
96544 KB |
Output is correct |
30 |
Correct |
532 ms |
97968 KB |
Output is correct |
31 |
Correct |
365 ms |
99708 KB |
Output is correct |
32 |
Correct |
373 ms |
94188 KB |
Output is correct |
33 |
Correct |
337 ms |
94512 KB |
Output is correct |
34 |
Correct |
544 ms |
90040 KB |
Output is correct |
35 |
Correct |
481 ms |
90608 KB |
Output is correct |
36 |
Correct |
639 ms |
89428 KB |
Output is correct |
37 |
Correct |
694 ms |
98404 KB |
Output is correct |
38 |
Correct |
779 ms |
94840 KB |
Output is correct |
39 |
Correct |
515 ms |
101120 KB |
Output is correct |
40 |
Correct |
608 ms |
99384 KB |
Output is correct |
41 |
Correct |
541 ms |
99380 KB |
Output is correct |
42 |
Correct |
767 ms |
91820 KB |
Output is correct |
43 |
Correct |
725 ms |
92928 KB |
Output is correct |
44 |
Correct |
934 ms |
94088 KB |
Output is correct |
45 |
Correct |
890 ms |
93276 KB |
Output is correct |
46 |
Correct |
910 ms |
88744 KB |
Output is correct |
47 |
Correct |
772 ms |
86820 KB |
Output is correct |
48 |
Correct |
648 ms |
85716 KB |
Output is correct |
49 |
Correct |
686 ms |
85284 KB |
Output is correct |
50 |
Correct |
679 ms |
95208 KB |
Output is correct |
51 |
Correct |
74 ms |
70368 KB |
Output is correct |
52 |
Correct |
79 ms |
70752 KB |
Output is correct |
53 |
Correct |
642 ms |
96304 KB |
Output is correct |
54 |
Correct |
730 ms |
98456 KB |
Output is correct |
55 |
Correct |
785 ms |
96512 KB |
Output is correct |
56 |
Correct |
767 ms |
98440 KB |
Output is correct |
57 |
Correct |
70 ms |
70348 KB |
Output is correct |
58 |
Correct |
79 ms |
70692 KB |
Output is correct |
59 |
Correct |
556 ms |
93972 KB |
Output is correct |
60 |
Correct |
908 ms |
94896 KB |
Output is correct |
61 |
Correct |
823 ms |
94852 KB |
Output is correct |
62 |
Correct |
776 ms |
94680 KB |
Output is correct |
63 |
Correct |
796 ms |
94356 KB |
Output is correct |
64 |
Correct |
900 ms |
94916 KB |
Output is correct |
65 |
Correct |
825 ms |
94488 KB |
Output is correct |
66 |
Correct |
751 ms |
92532 KB |
Output is correct |
67 |
Correct |
760 ms |
94104 KB |
Output is correct |
68 |
Correct |
605 ms |
97512 KB |
Output is correct |
69 |
Correct |
579 ms |
99392 KB |
Output is correct |
70 |
Correct |
741 ms |
92116 KB |
Output is correct |
71 |
Correct |
882 ms |
97740 KB |
Output is correct |