제출 #653569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653569		cadmiumsky	Event Hopping (BOI22_events)	C++14	0 / 100	286 ms	28632 KiB

events

#include <bits/stdc++.h>
#warning Instant WA
#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);
}

#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 solve(vector<int> V) {
    vector<tii> aggr;
    vector<int> tmprez(q, 0);
    
    for(auto i : V) {
      auto [f, s] = bruteqs[i];
      int lim1 = 0;
      for(int i = 16; i >= 0; i--) {
	if(lim1 + (1 << i) >= highway.size()) continue;
	if(highway[lim1 + (1 << i)].r < segm[f].r)
	  lim1 += (1 << i);
      }
      lim1++;
      
      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].r)
	  lim2 += (1 << i);
      }
      if(segm[s] == highway[lim2])
	lim2--;
      int l1, r1, l2, r2;
      tie(l2, r2) = segm[s];
      //cerr << lim1 << ' ' << lim2 << '\n';
      rez[i] = lim2 - lim1 + 1;
      if(lim1 == lim2) {
	tie(l1, r1) = segm[f];
      }
      else {
	tie(l1, r1) = highway[lim2];
      }
      
      //cerr << "for " << i << "( " << f << ' ' << s << ") " << l1 << ' ' << r1 << '/' << l2 << ' ' << r2 << '\n';
      aggr.emplace_back(l1 - 1, l2, -r2);
      aggr.emplace_back(r1, l2, r2);
    }
    
    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);
    //cerr << "imi place sa fac sex\n" << sz(V) << '\n';
    auto advance = [&](int& ptr) {
      int atr = V[ind[ptr] / 2];
      //cerr << ptr << ' ' << ind[ptr] << ' ' << V[ptr] << '\n';
      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);
	//cerr << "for " << atr << ' ' << "there are " << tmprez[atr] << "possibilities\n"; 
	if(tmprez[atr] == 0)
	  rez[atr] = 0;
	else
	  rez[atr]++;
      }
      ptr++;
    };
    int ptr = 0;
    
    for(auto [x, y] : cpsegm) {
      //cerr << x << ' ' << y << '\n';
      while(ptr < sz(ind) && get<0>(aggr[ind[ptr]]) < x) {
	advance(ptr);
      }
      aib.upd(y);
      //cerr << "added on " << y << '\n';
    }
    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';
  
  //exit(0);
  //1 5
//1 2
//3 4
//5 8
//6 7
//8 10
//9 10
//11 12

  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);
    if(a == 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';
  }
  
}

컴파일 시 표준 에러 (stderr) 메시지

events.cpp:2:2: warning: #warning Instant WA [-Wcpp]
    2 | #warning Instant WA
      |  ^~~~~~~
events.cpp: In function 'void Driver::solve(std::vector<int>)':
events.cpp:55:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |       auto [f, s] = bruteqs[i];
      |            ^
events.cpp:58: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]
   58 |  if(lim1 + (1 << i) >= highway.size()) continue;
      |     ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
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(lim2 + (1 << i) >= highway.size()) continue;
      |     ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
events.cpp: In lambda function:
events.cpp:101:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |       auto [line, l, r] = aggr[ind[ptr]];
      |            ^
events.cpp: In function 'void Driver::solve(std::vector<int>)':
events.cpp:118:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |     for(auto [x, y] : cpsegm) {
      |              ^
events.cpp:120:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |       while(ptr < sz(ind) && get<0>(aggr[ind[ptr]]) < x) {
      |                 ^
events.cpp:126:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     while(ptr < sz(ind)) {
      |               ^
events.cpp: In function 'int main()':
events.cpp:140:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |   for(auto &[a, b] : segm) cin >> a >> b, nrm[a], nrm[b];
      |             ^
events.cpp:141:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |   int cnt = 1; for(auto &[a, b] : nrm) b = cnt++;
      |                          ^
events.cpp:142:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  142 |   for(auto &[a, b] : segm) tie(a, b) = pii{nrm[a], nrm[b]};
      |             ^
events.cpp:167:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  167 |   for(auto &[a, b] : bruteqs) {
      |             ^

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