oj.uz

Submission #653608

# Submission time Handle Problem Language Result Execution time Memory
653608 2022-10-27T11:36:44 Z cadmiumsky Event Hopping (BOI22_events) C++14
10 / 100
 389 ms 18248 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 = 1e5 + 5;

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 lsb(x) (x & -x)
struct AIB {
  int tree[nmax * 2];  
  int len;
  void init(int nlen) {
    len = nlen;
    memset(tree, 0, sizeof(tree[0]) * (len + 1));
  }
  void upd(int p, int x = 1) {
    while(p <= len)
      tree[p] += x,
      p += lsb(p);
  }
  int query(int p) {
    int sum = 0;
    while(p > 0)
      sum += tree[p],
      p -= lsb(p);
    return sum;
  }
  int query(int l, int r) { return query(r) - query(l - 1); }
};

namespace Driver {
  void solve(vector<int> V) {
    vector<tii> aggr;
    vector<int> tmprez(q, 0);
    vector<int> spart(sz(highway));
    for(int i = 1; i < sz(highway); i++)
      if(highway[i].l > highway[i - 1].r)
	spart[i] = spart[i - 1] + 1;
      else
	spart[i] = spart[i - 1];
    
    for(int i = 0; i < sz(V); i++) {
      auto [f, s] = bruteqs[V[i]];
      int lim1 = 0;
      for(int i = 16; i >= 0; i--) {
	if(lim1 + (1 << i) >= highway.size()) continue;
	if(highway[lim1 + (1 << i)].l <= segm[f].r)
	  lim1 += (1 << i);
      }
      
      int lim2 = 0;
      for(int i = 16; i >= 0; i--) {
	if(lim2 + (1 << i) >= highway.size()) continue;
	if(highway[lim2 + (1 << i)].r < segm[s].l)
	  lim2 += (1 << i);
      }
      lim2++;
      
      //cerr << lim1 << ' ' << lim2 << '\n';
      //cerr << f << ' ' << s << "\n";
      //cerr << highway[lim1].l << ' ' << highway[lim1].r << '\t' << highway[lim2].l << ' ' << highway[lim2].r << "\n";
      //cerr << segm[f].l << ' ' << segm[f].r << '\t' << segm[s].l << ' ' << segm[s].r << "\n\n";
      if(spart[lim2] - spart[lim1] > 0) {
	rez[V[i]] = 0;
	swap(V[i], V.back());
	V.pop_back();
	i--;
	continue;
      }
	
      if(intersecc(segm[s], highway[lim2]) && intersecc(highway[lim1], segm[f])) {
	rez[V[i]] = lim2 - lim1 + 2;
	//cerr << "here\n";
	//cerr << rez[0] << '\n';
	swap(V[i], V.back());
	V.pop_back();
	i--;
	continue;
      }
      
      int l1, r1, l2, r2;
      tie(l2, r2) = segm[s];
      tie(l1, r1) = highway[lim2 - 1];
      
      aggr.emplace_back(l1 - 1, l2, -r2);
      aggr.emplace_back(r1, l2, r2);
      //cerr << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
    }
    
    vector<int> ind(sz(aggr));
    iota(all(ind), 0);
    //for(auto &x : ind) x /= 2;
    sort(all(ind), [&](auto a, auto b) { return aggr[a] < aggr[b]; });
    vector<pii> cpsegm = segm;
    sort(all(cpsegm));
    
    AIB aib;
    aib.init(2 * n);
    
    auto advance = [&](int& ptr) {
      int atr = V[ind[ptr] / 2];
      auto [line, l, r] = aggr[ind[ptr]];
      if(r < 0) {
	r = -r;
	tmprez[atr] = -aib.query(l, r);
      }
      else {
	tmprez[atr] += aib.query(l, r);
	if(tmprez[atr] == 0)
	  rez[atr] = 0;
	else
	  rez[atr]++;
      }
      ptr++;
    };
    int ptr = 0;
    
    for(auto [x, y] : cpsegm) {
      while(ptr < sz(ind) && get<0>(aggr[ind[ptr]]) < x)
	advance(ptr);
      aib.upd(y);
    }
    while(ptr < sz(ind)) {
      advance(ptr);
    }
    return;
  }
}

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]};
  sort(all(ind), [&](int a, int b) { return segm[a].l < segm[b].l || (segm[a].l == segm[b].l && segm[a].r > segm[b].r); });
  
  highway.emplace_back(-1, -1);
  for(auto i : ind) {
    if(highway.size() == 1 || (highway.size() >= 2 && segm[i].l > highway.rbegin()[1].r && segm[i].r > highway.back().r))
      highway.emplace_back(segm[i]);
    else if(highway.back().r < segm[i].r)
      highway.back() = segm[i];
  }
  //for(auto [a, b] : highway) cerr << a << ' ' << b << '\n';

  vector<int> tosolve;
  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 {
      tosolve.push_back(rez.size());
      rez.push_back(0);
    }	
  }
  
  Driver::solve(tosolve);
  
  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 'void Driver::solve(std::vector<int>)':
events.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i = 1; i < sz(highway); i++)
      |                      ^
events.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < sz(V); i++) {
      |                      ^
events.cpp:63:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |       auto [f, s] = bruteqs[V[i]];
      |            ^
events.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  if(lim1 + (1 << i) >= highway.size()) continue;
      |     ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
events.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  if(lim2 + (1 << i) >= highway.size()) continue;
      |     ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
events.cpp: In lambda function:
events.cpp:122:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |       auto [line, l, r] = aggr[ind[ptr]];
      |            ^
events.cpp: In function 'void Driver::solve(std::vector<int>)':
events.cpp:138:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |     for(auto [x, y] : cpsegm) {
      |              ^
events.cpp:139:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |       while(ptr < sz(ind) && get<0>(aggr[ind[ptr]]) < x)
      |                 ^
events.cpp:143:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     while(ptr < sz(ind)) {
      |               ^
events.cpp: In function 'int main()':
events.cpp:157:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  157 |   for(auto &[a, b] : segm) cin >> a >> b, nrm[a], nrm[b];
      |             ^
events.cpp:158:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  158 |   int cnt = 1; for(auto &[a, b] : nrm) b = cnt++;
      |                          ^
events.cpp:159:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  159 |   for(auto &[a, b] : segm) tie(a, b) = pii{nrm[a], nrm[b]};
      |             ^
events.cpp:173:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  173 |   for(auto &[a, b] : bruteqs) {
      |             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 304 ms 11684 KB Output is correct
3 Correct 315 ms 11940 KB Output is correct
4 Correct 316 ms 11588 KB Output is correct
5 Correct 339 ms 12780 KB Output is correct
6 Correct 273 ms 12940 KB Output is correct
7 Correct 283 ms 13652 KB Output is correct
8 Correct 352 ms 18248 KB Output is correct
9 Correct 332 ms 16940 KB Output is correct
10 Correct 329 ms 11444 KB Output is correct
11 Correct 304 ms 13112 KB Output is correct
12 Correct 206 ms 11220 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 11640 KB Output is correct
2 Correct 272 ms 11908 KB Output is correct
3 Correct 289 ms 11532 KB Output is correct
4 Correct 350 ms 17000 KB Output is correct
5 Correct 352 ms 11348 KB Output is correct
6 Incorrect 389 ms 14652 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 304 ms 11684 KB Output is correct
3 Correct 315 ms 11940 KB Output is correct
4 Correct 316 ms 11588 KB Output is correct
5 Correct 339 ms 12780 KB Output is correct
6 Correct 273 ms 12940 KB Output is correct
7 Correct 283 ms 13652 KB Output is correct
8 Correct 352 ms 18248 KB Output is correct
9 Correct 332 ms 16940 KB Output is correct
10 Correct 329 ms 11444 KB Output is correct
11 Correct 304 ms 13112 KB Output is correct
12 Correct 206 ms 11220 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 980 KB Output is correct
15 Correct 2 ms 1108 KB Output is correct
16 Correct 2 ms 1108 KB Output is correct
17 Incorrect 2 ms 1108 KB Output isn't correct
18 Halted 0 ms 0 KB -