Submission #1111607

#TimeUsernameProblemLanguageResultExecution timeMemory
1111607hmm789Fire (BOI24_fire)C++14
74 / 100
2031 ms311876 KiB
#include <bits/stdc++.h> using namespace std; #define int long long struct node { int s, e, m, v, lz; node *l, *r; node(int _s, int _e) { s = _s, e = _e, m = (s+e)/2, v = 0, lz = -1; if(s != e) { l = new node(s, m); r = new node(m+1, e); } } void prop() { if(lz == -1) return; v = lz; if(s != e) { l->lz = lz; r->lz = lz; } lz = -1; } void update(int x, int y, int val) { prop(); if(x <= s && e <= y) {lz = val; return;} else if(x > m) r->update(x, y, val); else if(y <= m) l->update(x, y, val); else l->update(x, y, val), r->update(x, y, val); l->prop(); r->prop(); v = max(l->v, r->v); } int get(int x) { prop(); if(s == e) return v; else if(x > m) return r->get(x); else return l->get(x); } } *root, *root2; vector<int> adj[800000]; int p[800000][20], depth[800000]; bool v[800000]; void dfs(int x, int pa, int d) { v[x] = 1; depth[x] = d; p[x][0] = pa; for(int i = 1; i < 20; i++) { if(p[x][i-1] == -1) break; p[x][i] = p[p[x][i-1]][i-1]; } for(int i : adj[x]) if(!v[i]) dfs(i, x, d+1); } int getp(int x, int k) { for(int i = 0; i < 20; i++) { if(k&(1<<i)) x = p[x][i]; } return x; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, x, y; cin >> n >> m; n *= 2; pair<int, int> a[n]; vector<int> dis, dis2, act; for(int i = 0; i < n; i++) { if(i < n/2) { cin >> x >> y; if(y < x) y = y+m; a[i] = {y, x}; dis.push_back(x); dis.push_back(y); } else { a[i].first = a[i-n/2].first+m; a[i].second = a[i-n/2].second+m; dis.push_back(a[i].first); dis.push_back(a[i].second); } } sort(dis.begin(), dis.end()); dis.erase(unique(dis.begin(), dis.end()), dis.end()); for(int i : dis) act.push_back(i); root = new node(0, dis.size()); for(int i = 0; i < n; i++) { a[i].first = lower_bound(dis.begin(), dis.end(), a[i].first)-dis.begin(); a[i].second = lower_bound(dis.begin(), dis.end(), a[i].second)-dis.begin(); } sort(a, a+n); for(int i = 0; i < n; i++) { root->update(a[i].second, a[i].first, a[i].first); } int par[dis.size()]; for(int i = 0; i < dis.size(); i++) { if(root->get(i) != i) adj[root->get(i)].push_back(i); par[i] = root->get(i); } memset(p, -1, sizeof(p)); for(int i = dis.size()-1; i >= 0; i--) if(!v[i]) { dfs(i, -1, 0); } int l = 0, r = n+1, md; while(l < r) { md = (l+r)/2; bool ok = false; for(int i = 0; i < dis.size()-1; i++) { if(act[getp(i, min(md, depth[i]))]-act[i] >= m) ok = true; } if(ok) r = md; else l = md+1; } if(l == n+1) cout << -1 << '\n'; else cout << l << '\n'; }

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:100:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i = 0; i < dis.size(); i++) {
      |                 ~~^~~~~~~~~~~~
Main.cpp:112:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   for(int i = 0; i < dis.size()-1; i++) {
      |                  ~~^~~~~~~~~~~~~~
Main.cpp:99:6: warning: variable 'par' set but not used [-Wunused-but-set-variable]
   99 |  int par[dis.size()];
      |      ^~~
#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...