제출 #593867

#제출 시각아이디문제언어결과실행 시간메모리
593867vovikRailway Trip 2 (JOI22_ho_t4)C++17
100 / 100
958 ms101204 KiB
#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) { print(ans); } else { print("-1"); } } }

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

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) {
      |                         ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...