제출 #944068

#제출 시각아이디문제언어결과실행 시간메모리
944068panEvent Hopping (BOI22_events)C++17
0 / 100
219 ms42532 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#include "bits_stdc++.h" #define f first #define s second #define pb push_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define input(x) scanf("%lld", &x); #define input2(x, y) scanf("%lld%lld", &x, &y); #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z); #define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a); #define print(x, y) printf("%lld%c", x, y); #define show(x) cerr << #x << " is " << x << endl; #define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl; #define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl; #define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); using namespace std; //using namespace __gnu_pbds; //#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> //#define ordered_multiset tree<int, null_type, less_equal<int>, srb_tree_tag, tree_order_statistics_node_update> typedef long long ll; typedef long double ld; typedef pair<ld, ll> pd; typedef pair<string, ll> psl; typedef pair<ll, ll> pi; typedef pair<pi, ll> pii; ll const INF = 1e13; bool compare(pii a, pii b) { if (a.f.s==b.f.s) return a.f.f<b.f.f; return a.f.s<b.f.s; } // RMQ struct node { int s, e, m; pi val; node * l, * r; node(int S, int E) { s = S, e = E, m = (s + e) / 2; val = mp(INF, -1); if (s != e) { l = new node(s, m); r = new node(m + 1, e); } } void update(int X, pi V) { if (s == e) {val = min(val, V);} else { if (X <= m) l -> update(X, V); else r -> update(X, V); val = max(val = l -> val, r -> val); } } pi query(int S, int E) { if (s == S && e == E) return val; else if (E <= m) return l -> query(S, E); else if (S >= m + 1) return r -> query(S, E); else return min(l -> query(S, m), r -> query(m + 1, E)); } }* root; // Twok decomp ll twok[100005][25]; int main() { ll n,q, l, r; input2(n,q); vector<pii> eve(n); vector<pi> save(n); vector<ll> dis; for (ll i=0; i<n; ++i) {input2(save[i].f, save[i].s); eve[i] = mp(save[i], i); dis.pb(save[i].f), dis.pb(save[i].s);} discretize(dis); sort(eve.begin(), eve.end(), compare); root = new node(0, dis.size()-1); for (ll i=0; i<n; ++i) { ll l = lb(dis.begin(), dis.end(), eve[i].f.f)-dis.begin(), r = lb(dis.begin(), dis.end(), eve[i].f.s)-dis.begin(), ind = eve[i].s; root->update(r, mp(l, ind)); pi nxt = root->query(l, r); if (nxt.f>=l) twok[ind][0] = -1; else twok[ind][0] = nxt.s; } for (ll k=1; k<20; ++k) { for (ll x = 0; x<n; ++x) { if (twok[x][k-1]==-1) twok[x][k]=-1; else twok[x][k] = twok[twok[x][k-1]][k-1]; } } while (q--) { input2(l, r); l--; r--; ll ans = 0; if (l==r) {print(0LL, '\n'); continue;} if (save[l].s>save[r].s){ cout << "impossible" << '\n'; continue;} if (save[r].f<=save[l].s) print(1LL, '\n'); for (ll i=19; i>=0; --i) { if (twok[r][i]==-1) continue; if (save[twok[r][i]].f<= save[l].s) continue; r = twok[r][i]; ans += (1LL<<i); } if (twok[r][0]==-1) {cout << "impossible" << endl; continue;} print(ans+2, '\n'); } return 0; }

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

events.cpp: In function 'int main()':
events.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
events.cpp:71:2: note: in expansion of macro 'input2'
   71 |  input2(n,q);
      |  ^~~~~~
events.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
events.cpp:75:26: note: in expansion of macro 'input2'
   75 |  for (ll i=0; i<n; ++i) {input2(save[i].f, save[i].s); eve[i] = mp(save[i], i); dis.pb(save[i].f), dis.pb(save[i].s);}
      |                          ^~~~~~
events.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
events.cpp:97:3: note: in expansion of macro 'input2'
   97 |   input2(l, r);
      |   ^~~~~~
#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...