Submission #653628

#	Time	Username	Problem	Language	Result	Execution time	Memory
653628		cadmiumsky	Event Hopping (BOI22_events)	C++14	10 / 100	469 ms	29048 KiB

events

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (x).size()
#define l first
#define r second
#define boo bool

using namespace std;
using pii = pair<int,int>;
using tii = tuple<int,int,int>;

int n, q;

vector<pii> highway;
vector<pii> segm;
vector<int> rez;
vector<pii> bruteqs;

const int nmax = 2e5 + 5;

int occ[nmax];
boo intersect(pii a, pii b) {
  return !(a.r < b.l || b.r < a.l);
}
boo intersecc(pii a, pii b) {
  return a.l <= b.r && b.r <= a.r;
}
 
#define ends adsjkhajksdhjkakjcss
vector<tii> qs[nmax];
vector<int> ends[nmax];

int main() {
  cin >> n >> q;
  
  segm.resize(n);
  vector<int> ind(n);
  iota(all(ind), 0);
  map<int,int> nrm;
  for(auto &[a, b] : segm) cin >> a >> b, nrm[a], nrm[b];
  int cnt = 1; for(auto &[a, b] : nrm) b = cnt++;
  for(auto &[a, b] : segm) tie(a, b) = pii{nrm[a], nrm[b]}, ends[b].push_back(a);
  
  bruteqs.resize(q);
  for(auto &[a, b] : bruteqs) {
    cin >> a >> b;
    --a;
    --b;
    if(segm[a].r > segm[b].r)
      rez.push_back(0);
    else if(segm[a] == segm[b])
      rez.push_back(-1);
    else if(intersect(segm[a], segm[b]))
      rez.push_back(1);
    else {
      rez.push_back(0);   
      qs[segm[b].r].emplace_back(segm[a].r, segm[b].l, rez.size() - 1);
    }
  }
  
  vector<pii> st;
  vector<int> sum;
  st.emplace_back(-1, -1);
  sum.emplace_back(0);
  
  for(int i = 1; i < cnt; i++) {
    int mn = i;
    for(auto x : ends[i]) mn = min(x, mn);
    //cerr << '\n';
    //cerr << mn << '\n';
    //cerr << '\n';
    while(!st.empty() && (mn <= st.back().l || (st.size() >= 2 && st.rbegin()[1].r >= mn)))
      sum.pop_back(),
      st.pop_back();
    if(mn > st.back().r)
      sum.emplace_back(sum.back() + 1);
    else
      sum.emplace_back(sum.back());
    st.emplace_back(mn, i);
    for(auto [a, b, id] : qs[i]) {
      int lim = 0;
      for(int i = 16; i >= 0; i--) {
	if(lim + (1 << i) >= st.size()) continue;
	if(st[lim + (1 << i)].l <= a)
	  lim += (1 << i);
      }
      if(sum.back() - sum[lim]) {
	//for(auto [a, b] : st) cerr << a << ' ' << b << '\n';
	//cerr << a << ' ' << b << ' ' << id << '\n';
	//cerr << sum.back() << ' ' << sum[lim] << '\n' << lim << '\n';
	rez[id] = 0;
      }
      else {
	rez[id] = st.size() - lim + (b > st.rbegin()[1].r);
      }
    }
  }
  
  for(auto x : rez) {
    if(x == 0) cout << "impossible\n";
    else if(x == -1) cout << "0\n";
    else cout << x << '\n';
  }
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:40:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |   for(auto &[a, b] : segm) cin >> a >> b, nrm[a], nrm[b];
      |             ^
events.cpp:41:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |   int cnt = 1; for(auto &[a, b] : nrm) b = cnt++;
      |                          ^
events.cpp:42:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |   for(auto &[a, b] : segm) tie(a, b) = pii{nrm[a], nrm[b]}, ends[b].push_back(a);
      |             ^
events.cpp:45:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |   for(auto &[a, b] : bruteqs) {
      |             ^
events.cpp:80:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     for(auto [a, b, id] : qs[i]) {
      |              ^
events.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  if(lim + (1 << i) >= st.size()) continue;
      |     ~~~~~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30