제출 #729617

#제출 시각아이디문제언어결과실행 시간메모리
729617Sam_a17Event Hopping (BOI22_events)C++17
50 / 100
1502 ms37096 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> 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 __builtin_popcount #define pb push_back #define popf pop_front #define popb pop_back #define ld long double #define ll long long 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(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 << "]"; } template <class T, class V> void print(unordered_map <T, V> v) { cerr << "[ "; for (auto i : v) { print(i); cerr << " "; } cerr << "]"; } template <class T> void print(deque <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; } #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define nl '\n' // for random generations mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count()); // mt19937 myrand(131); // 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 == "input") { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } else { // freopen("skis.in", "r", stdin); // freopen("skis.out", "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, M = 5e3 + 10, inf = 1e8, LOG = 18; int n, q, ord[N]; long long down[N][LOG]; struct node { long long l, r; long long id; bool operator<(const node &y) const { return l < y.l; } }; vector<node> intervals; struct segTreeMin { vector<pair<long long, int>> mTree; int size; void init(long long n) { size = 1; while(size < n) { size *= 2; } mTree.assign(2 * size - 1, {INT64_MAX, -1}); } void upd(int u, long long v, int ind, int x, int lx, int rx) { // set value at pos u if(rx - lx == 1) { mTree[x] = min(mTree[x], make_pair(v, ind)); return; } int m = (lx + rx) / 2; if(u < m) { upd(u, v, ind, 2 * x + 1, lx, m); }else { upd(u, v, ind, 2 * x + 2, m, rx); } mTree[x] = min(mTree[2 * x + 1], mTree[2 * x + 2]); } void upd(int u, long long v, int ind) { upd(u, v, ind, 0, 0, size); } pair<long long, int> qry (int l, int r, int x, int lx, int rx) { // range queries if(l >= rx || lx >= r) { return {INT64_MAX, -1}; } 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 min(s1, s2); } auto qry(int l, int r) { return qry(l, r, 0, 0, size); } }; segTreeMin seg_min; void solve_() { cin >> n >> q; vector<int> compress; for(int i = 1; i <= n; i++) { int li, ri; cin >> li >> ri; intervals.push_back({li, ri, i}); // compress.push_back(li); compress.push_back(ri); } sort(all(compress)); uniq(compress); sort(all(intervals)); seg_min.init(sz(compress) + 5); for(int i = 0; i < n; i++) { intervals[i].l = lower_bound(all(compress), intervals[i].l) - compress.begin() + 1; intervals[i].r = lower_bound(all(compress), intervals[i].r) - compress.begin() + 1; seg_min.upd(intervals[i].r, intervals[i].l, i); ord[intervals[i].id] = i; } for(int i = 0; i < n; i++) { for(int j = 0; j < LOG; j++) { down[i][j] = -1; } } for(int i = 1; i < n; i++) { auto ans = seg_min.qry(intervals[i].l, intervals[i].r + 1); if(ans.first < intervals[i].l) { down[i][0] = ans.second; } } for(int i = 1; i < LOG; i++) { for(int j = 0; j < n; j++) { if(down[j][i - 1] == -1) { down[j][i] = -1; continue; } down[j][i] = down[down[j][i - 1]][i - 1]; } } for(int i = 0; i < n; i++) { dbg(make_pair(intervals[i].l, intervals[i].r)) } while(q--) { int x, y; cin >> x >> y; x = ord[x], y = ord[y]; if(x == y) { cout << 0 << '\n'; continue; } if(intervals[x].r == intervals[y].r) { cout << 1 << '\n'; continue; } if(intervals[x].r > intervals[y].r) { cout << "impossible" << '\n'; continue; } int curr = y, aa = 0; for(int i = LOG - 1; i >= 0; i--) { if(down[curr][i] == -1) continue; if(intervals[down[curr][i]].l > intervals[x].r) { curr = down[curr][i]; aa += 1 << i; } } if(down[curr][0] == -1) { if(intervals[curr].l > intervals[x].r) { cout << "impossible" << '\n'; } else { cout << aa + 1 << '\n'; } } else { aa += 1; if(intervals[curr].l > intervals[x].r) { cout << aa + 1 << '\n'; } else { cout << aa << '\n'; } } } } int main() { setIO(); auto solve = [&](int test_case)-> void { for (int i = 1; i <= test_case; i++) { solve_(); } }; int test_cases = 1; // cin >> test_cases; solve(test_cases); return 0; }

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

events.cpp: In function 'void setIO(std::string)':
events.cpp:69:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:70:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   freopen("output.txt", "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...