oj.uz

Submission #653626

# Submission time Handle Problem Language Result Execution time Memory
653626 2022-10-27T12:51:15 Z cadmiumsky Event Hopping (BOI22_events) C++14
10 / 100
 326 ms 28868 KB 
#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)
      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 {
	//for(auto [a, b] : st) cerr << a << ' ' << b << '\n';
	//cerr << a << ' ' << b << ' ' << id << '\n';
	//cerr << st.size() << ' ' << lim << ' ' << (b != mn) << '\n';

	rez[id] = st.size() - lim + (b != mn);
      }
    }
  }
  
  for(auto x : rez) {
    if(x == 0) cout << "impossible\n";
    else if(x == -1) cout << "0\n";
    else cout << x << '\n';
  }
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 240 ms 23784 KB Output is correct
3 Correct 236 ms 23616 KB Output is correct
4 Correct 233 ms 23652 KB Output is correct
5 Correct 236 ms 24080 KB Output is correct
6 Correct 248 ms 24424 KB Output is correct
7 Correct 257 ms 24680 KB Output is correct
8 Correct 269 ms 28864 KB Output is correct
9 Correct 307 ms 28868 KB Output is correct
10 Correct 233 ms 23644 KB Output is correct
11 Correct 296 ms 25308 KB Output is correct
12 Correct 158 ms 21720 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9740 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Incorrect 6 ms 9684 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9740 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Incorrect 6 ms 9684 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9740 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Incorrect 6 ms 9684 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 23848 KB Output is correct
2 Correct 263 ms 23660 KB Output is correct
3 Correct 266 ms 23640 KB Output is correct
4 Correct 299 ms 28852 KB Output is correct
5 Correct 259 ms 23552 KB Output is correct
6 Incorrect 326 ms 28164 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 240 ms 23784 KB Output is correct
3 Correct 236 ms 23616 KB Output is correct
4 Correct 233 ms 23652 KB Output is correct
5 Correct 236 ms 24080 KB Output is correct
6 Correct 248 ms 24424 KB Output is correct
7 Correct 257 ms 24680 KB Output is correct
8 Correct 269 ms 28864 KB Output is correct
9 Correct 307 ms 28868 KB Output is correct
10 Correct 233 ms 23644 KB Output is correct
11 Correct 296 ms 25308 KB Output is correct
12 Correct 158 ms 21720 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 6 ms 9740 KB Output is correct
16 Correct 6 ms 9812 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Incorrect 6 ms 9684 KB Output isn't correct
19 Halted 0 ms 0 KB -