제출 #735789

#제출 시각아이디문제언어결과실행 시간메모리
735789Sam_a17Railway Trip 2 (JOI22_ho_t4)C++17
27 / 100
2070 ms158552 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> //#include "temp.cpp" #include <cstdio> using namespace std; #ifndef ONLINE_JUDGE #define dbg(x) cerr << #x <<" "; print(x); cerr << endl; #else #define dbg(x) #endif #define sz(x) (int((x).size())) #define len(x) (int)x.length() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define clr(x) (x).clear() #define uniq(x) x.resize(unique(all(x)) - x.begin()); #define blt(x) __builtin_popcount(x) #define pb push_back #define popf pop_front #define popb pop_back void print(long long t) {cerr << t;} void print(int t) {cerr << t;} void print(string t) {cerr << t;} void print(char t) {cerr << t;} void print(double t) {cerr << t;} void print(long double t) {cerr << t;} void print(unsigned long long t) {cerr << t;} template <class T, class V> void print(pair <T, V> p); template <class T> void print(vector <T> v); template <class T> void print(set <T> v); template <class T, class V> void print(map <T, V> v); template <class T> void print(multiset <T> v); template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";} template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";} template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define nl '\n' // for grid problems int dx[8] = {-1,0,1,0,1,-1,1,-1}; int dy[8] = {0,1,0,-1,1,1,-1,-1}; // lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6 void fastIO() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } // file in/out void setIO(string str = "") { fastIO(); if (str != "") { freopen((str + ".in").c_str(), "r", stdin); freopen((str + ".out").c_str(), "w", stdout); } } // Indexed Set template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 2e5 + 10, LOG = 17; multiset<int> to_add[N], to_erase[N]; multiset<int> add[N], rase[N]; int n, k, m, q, l[N], r[N]; pair<long long, long long> up[N][LOG]; // segment Tree Max // Range Queries struct segTree { vector<pair<long long, long long>> mTree; int size; void init(long long n) { size = 1; while(size < n) { size *= 2; } mTree.assign(2 * size - 1, {INT64_MAX, INT64_MIN}); } pair<long long, long long> combine(pair<long long, long long> a, pair<long long, long long> b) { return make_pair(min(a.first, b.first), max(a.second, b.second)); } void upd(int u, long long li, long long ri, int x, int lx, int rx) { // set value at pos u if(rx - lx == 1) { mTree[x] = {li, ri}; return; } int m = (lx + rx) / 2; if(u < m) { upd(u, li, ri, 2 * x + 1, lx, m); }else { upd(u, li, ri, 2 * x + 2, m, rx); } mTree[x] = combine(mTree[2 * x + 1], mTree[2 * x + 2]); } void upd(int u, long long li, long long ri) { upd(u, li, ri, 0, 0, size); } pair<long long, long long> qry (int l, int r, int x, int lx, int rx) { // range queries if(l >= rx || lx >= r) { return {INT64_MAX, INT64_MIN}; } if(lx >= l && r >= rx) { return mTree[x]; } int m = (rx + lx) / 2; auto s1 = qry(l, r, 2 * x + 1, lx, m); auto s2 = qry(l, r, 2 * x + 2, m, rx); return combine(s1, s2); } pair<long long, long long> qry(int l, int r) { return qry(l, r, 0, 0, size); } }; segTree seg_max[LOG]; void solve_() { cin >> n >> k; cin >> m; for(int i = 0; i < LOG; i++) { seg_max[i].init(n + 3); } for(int i = 1; i <= m; i++) { int s, t; cin >> s >> t; if(s < t) { int tt = min(t - 1, s + k - 1); to_add[s].insert(t); to_erase[tt + 1].insert(t); } else { // s > t int tt = max(t + 1, s - k + 1); add[s].insert(t); rase[tt - 1].insert(t); } } multiset<int> curr; for(int i = 1; i <= n; i++) { for(auto j: to_add[i]) { curr.insert(j); } for(auto j: to_erase[i]) { curr.erase(curr.find(j)); } if(!curr.empty()) { r[i] = max(i, *curr.rbegin()); } else { r[i] = i; } } curr.clear(); for(int i = n; i >= 1; i--) { for(auto j: add[i]) { curr.insert(j); } for(auto j: rase[i]) { curr.erase(curr.find(j)); } if(!curr.empty()) { l[i] = min(i, *curr.begin()); } else { l[i] = i; } } for(int i = 1; i <= n; i++) { up[i][0] = {l[i], r[i]}; seg_max[0].upd(i, l[i], r[i]); } for(int j = 1; j < LOG; j++) { for(int i = 1; i <= n; i++) { up[i][j] = seg_max[j - 1].qry(up[i][j - 1].first, up[i][j - 1].second + 1); seg_max[j].upd(i, up[i][j].first, up[i][j].second); } } // cin >> q; for(int i = 1; i <= q; i++) { int s, t; cin >> s >> t; int ina = 0, inb = n, ans = -2; pair<long long, long long> pr; while(ina <= inb) { int mid = (ina + inb) / 2; pr = {l[s], r[s]}; for(int j = 0; j < LOG; j++) { if(mid & (1 << j)) { auto uu = seg_max[j].qry(pr.first, pr.second + 1); pr.first = min(pr.first, uu.first); pr.second = max(pr.second, uu.second); } } if(t >= pr.first && t <= pr.second) { ans = mid; inb = mid - 1; } else { ina = mid + 1; } } cout << ans + 1 << '\n'; } } int main() { setIO(); auto solve = [&](int test_case)-> void { while(test_case--) { solve_(); } }; int test_cases = 1; // cin >> test_cases; solve(test_cases); return 0; }

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

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...