Submission #1048085

#TimeUsernameProblemLanguageResultExecution timeMemory
1048085sofijavelkovskaEvent Hopping (BOI22_events)C++17
0 / 100
107 ms12492 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=(1<<18), LOG=17, INF=1e9; int tree[2*MAXN-1]; int find(int x, int l, int r, int lt, int rt) { if (l>=rt || r<=lt) return INF; if (l>=lt && r<=rt) return tree[x]; return min(find(2*x+1, l, (l+r)/2, lt, rt), find(2*x+2, (l+r)/2, r, lt, rt)); } void update(int x, int l, int r, int index, int value) { if (l>index || r<=index) return; if (r-l==1) { tree[x]=min(tree[x], value); return; } update(2*x+1, l, (l+r)/2, index, value); update(2*x+2, (l+r)/2, r, index, value); tree[x]=min(tree[2*x+1], tree[2*x+2]); return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; int l[n], r[n]; for (int i=0; i<n; i++) cin >> l[i] >> r[i]; vector<int> temp; for (int i=0; i<n; i++) { temp.push_back(l[i]); temp.push_back(r[i]); } sort(temp.begin(), temp.end()); vector<int> compress; for (auto x : temp) if (compress.empty() || x!=compress.back()) compress.push_back(x); for (int i=0; i<2*MAXN-1; i++) tree[i]=INF; for (int i=0; i<n; i++) { int leftindex=lower_bound(compress.begin(), compress.end(), l[i])-compress.begin(); int rightindex=lower_bound(compress.begin(), compress.end(), r[i])-compress.begin(); update(0, 0, MAXN, rightindex, leftindex); } int prev[compress.size()]; for (int i=0; i<compress.size(); i++) prev[i]=-1; for (int i=0; i<n; i++) { int leftindex=lower_bound(compress.begin(), compress.end(), l[i])-compress.begin(); int rightindex=lower_bound(compress.begin(), compress.end(), r[i])-compress.begin(); prev[leftindex]=find(0, 0, MAXN, leftindex, rightindex+1); if (prev[leftindex]==leftindex) prev[leftindex]=-1; } int blift[compress.size()][LOG]; for (int i=0; i<compress.size(); i++) for (int j=0; j<LOG; j++) blift[i][j]=-1; for (int i=0; i<compress.size(); i++) blift[i][0]=prev[i]; for (int j=1; j<LOG; j++) for (int i=0; i<compress.size(); i++) if (blift[i][j-1]!=-1) blift[i][j]=blift[blift[i][j-1]][j-1]; /*for (int j=0; j<3; j++) { for (int i=0; i<compress.size(); i++) cout << blift[i][j] << ' '; cout << '\n'; }*/ while (q--) { int x, y; cin >> x >> y; x=x-1; y=y-1; if (x==y) { cout << 0 << '\n'; continue; } if (r[x]>r[y]) { cout << "impossible" << '\n'; continue; } int total=1; int i=lower_bound(compress.begin(), compress.end(), l[y])-compress.begin(); //cout << "x y " << x+1 << ' ' << y+1 << '\n'; //cout << "i " << compress[i] << '\n'; for (int j=LOG-1; j>=0; j--) if (blift[i][j]!=-1 && compress[blift[i][j]]>r[x]) { i=blift[i][j]; //cout << "i " << compress[i] << '\n'; total=total+(1<<j); } if (blift[i][0]!=-1 && compress[blift[i][0]]<=r[x]) cout << total+1 << '\n'; else cout << "impossible" << '\n'; } return 0; }

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i=0; i<compress.size(); i++)
      |                   ~^~~~~~~~~~~~~~~~
events.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i=0; i<compress.size(); i++)
      |                   ~^~~~~~~~~~~~~~~~
events.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i=0; i<compress.size(); i++)
      |                   ~^~~~~~~~~~~~~~~~
events.cpp:81:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int i=0; i<compress.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...