oj.uz

답안 #653643

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653643 2022-10-27T13:39:43 Z cadmiumsky Event Hopping (BOI22_events) C++14
0 / 100
 444 ms 31540 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];
#define lsb(x) (x & -x)
struct AIB {
  int tree[nmax];  
  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 init(vector<int> V, vector<tii> aggr) {
    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);
    vector<int> tmprez(q, 0);
  
    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];
	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);
    }
  }
}

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);
  
  vector<int> V;
  vector<tii> aggr;
  
  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';
    
    sort(all(qs[i]));
    for(auto [a, b, id] : qs[i]) {
      while(!st.empty() && (b <= st.back().l || (st.size() >= 2 && st.rbegin()[1].r >= b)))
	sum.pop_back(),
	st.pop_back();
      if(b > st.back().r)
	sum.emplace_back(sum.back() + 1);
      else
	sum.emplace_back(sum.back());
      st.emplace_back(b, 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]) {
	rez[id] = 0;
      }
      else {
	if(lim == st.size() - 2) {
	  rez[id] = 2;
	}
	else {
	  int l1, l2, r1, r2;
	  tie(l1, r1) = st[lim];
	  tie(l2, r2) = st[lim + 2];
	  aggr.emplace_back(l1 - 1, b, r2);
	  aggr.emplace_back(a, b, r2);
	  V.emplace_back(id);
	  rez[id] = st.size() - lim;
	}
      }
    }
    
    
    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);
  }
  
  Driver::init(V, aggr);
  
  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 lambda function:
events.cpp:70:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |       auto [line, l, r] = aggr[ind[ptr]];
      |            ^
events.cpp: In function 'void Driver::init(std::vector<int>, std::vector<std::tuple<int, int, int> >)':
events.cpp:86:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |     for(auto [x, y] : cpsegm) {
      |              ^
events.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |       while(ptr < sz(ind) && get<0>(aggr[ind[ptr]]) < x)
      |                 ^
events.cpp:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     while(ptr < sz(ind)) {
      |               ^
events.cpp: In function 'int main()':
events.cpp:104:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |   for(auto &[a, b] : segm) cin >> a >> b, nrm[a], nrm[b];
      |             ^
events.cpp:105:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |   int cnt = 1; for(auto &[a, b] : nrm) b = cnt++;
      |                          ^
events.cpp:106:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  106 |   for(auto &[a, b] : segm) tie(a, b) = pii{nrm[a], nrm[b]}, ends[b].push_back(a);
      |             ^
events.cpp:109:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |   for(auto &[a, b] : bruteqs) {
      |             ^
events.cpp:141:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |     for(auto [a, b, id] : qs[i]) {
      |              ^
events.cpp:152: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]
  152 |  if(lim + (1 << i) >= st.size()) continue;
      |     ~~~~~~~~~~~~~~~^~~~~~~~~~~~
events.cpp:160:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |  if(lim == st.size() - 2) {
      |     ~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 295 ms 31540 KB Output is correct
3 Correct 299 ms 31352 KB Output is correct
4 Correct 317 ms 31488 KB Output is correct
5 Correct 309 ms 31100 KB Output is correct
6 Correct 341 ms 31184 KB Output is correct
7 Correct 337 ms 31188 KB Output is correct
8 Incorrect 348 ms 30084 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 7 ms 10476 KB Output is correct
3 Correct 7 ms 10520 KB Output is correct
4 Correct 7 ms 10580 KB Output is correct
5 Correct 6 ms 10580 KB Output is correct
6 Incorrect 9 ms 10580 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 7 ms 10476 KB Output is correct
3 Correct 7 ms 10520 KB Output is correct
4 Correct 7 ms 10580 KB Output is correct
5 Correct 6 ms 10580 KB Output is correct
6 Incorrect 9 ms 10580 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 7 ms 10476 KB Output is correct
3 Correct 7 ms 10520 KB Output is correct
4 Correct 7 ms 10580 KB Output is correct
5 Correct 6 ms 10580 KB Output is correct
6 Incorrect 9 ms 10580 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 344 ms 30860 KB Output is correct
2 Correct 313 ms 30964 KB Output is correct
3 Correct 322 ms 30892 KB Output is correct
4 Correct 320 ms 29708 KB Output is correct
5 Correct 299 ms 25896 KB Output is correct
6 Incorrect 444 ms 31008 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 295 ms 31540 KB Output is correct
3 Correct 299 ms 31352 KB Output is correct
4 Correct 317 ms 31488 KB Output is correct
5 Correct 309 ms 31100 KB Output is correct
6 Correct 341 ms 31184 KB Output is correct
7 Correct 337 ms 31188 KB Output is correct
8 Incorrect 348 ms 30084 KB Output isn't correct
9 Halted 0 ms 0 KB -