Submission #937505

#	Time	Username	Problem	Language	Result	Execution time	Memory
937505		nguyentunglam	Golf (JOI17_golf)	C++17	100 / 100	2574 ms	286568 KiB

golf

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 1e5 + 10;

vector<int> rrhx, rrhy;

int st_x, st_y, ed_x, ed_y, n, m;

tuple<int, int, int> line[N << 2];

int d[N << 2];

queue<int> q;

struct IT {
  set<pair<int, int> > T[N << 3];
  void up(int s, int l, int r, int from, int to, pair<int, int> val) {
    if (l > to || r < from) return;
    if (from <= l && r <= to) {
      T[s].insert(val);
      return;
    }
    int mid = l + r >> 1;
    up(s << 1, l, mid, from, to, val);
    up(s << 1 | 1, mid + 1, r, from, to, val);
  }
  void get (int s, int l, int r, int pos, int from, int to, int val) {
    while (!T[s].empty()) {
      auto it = T[s].lower_bound(make_pair(from, 0));
      if (it == T[s].end()) break;
      if (it -> first > to) break;
      if (d[it -> second] == 0) {
        d[it -> second] = val;
        q.push(it -> second);
      }
      T[s].erase(it);
    }
    if (l == r) return;
    int mid = l + r >> 1;
    if (pos <= mid) get(s << 1, l, mid, pos, from, to, val);
    else get(s << 1 | 1, mid + 1, r, pos, from, to, val);
  }
} itx, ity;

struct square {
  int x1, x2, y1, y2;
};

square rect[N];

vector<tuple<int, int, int> > expand (vector<pair<int, int> > p) {
  vector<tuple<int, int, int> > event;
  set<pair<int, int> > s;
  for(int i = 1; i <= n; i++) if (rect[i].x1 + 1 < rect[i].x2) {
    event.emplace_back(rect[i].x1 + 1, rect[i].y1, rect[i].y2);
    event.emplace_back(rect[i].x2, rect[i].y1, rect[i].y2);

//    cout << rect[i].x1 + 1 << " " << rect[i].y1 << " " << rect[i].y2 << endl;
//    cout << rect[i].x2 - 1 << " " << rect[i].y1 << " " << rect[i].y2 << endl;
  }
  for(auto &[x, y] : p) {
    event.emplace_back(x, y, 0);
//    cout << x << " " << y << endl;
  }

  sort(all(event), [] (const tuple<int, int, int> &x, const tuple<int, int, int> &y) {
    if (get<0> (x) != get<0> (y)) return get<0> (x) < get<0> (y);
    return get<2> (x) > get<2> (y);
       });

  vector<tuple<int, int, int> > ret;

  for(auto &[x, y, z] : event) {
    if (z == 0) {
      auto it = s.lower_bound(make_pair(y, y));
      int l = 1, r = m;
//      cout << x << " " << y << " " << s.size() << endl;
      if (it != s.end()) r = it -> first;
      if (it != s.begin()) {
        it--;
        l = it -> second;
      }
      ret.emplace_back(x, l, r);
    }
    else {
      if (s.empty()) {
        s.insert(make_pair(y, z));
      }
      else {
        auto it = s.find(make_pair(y, z));
        if (it != s.end()) s.erase(it);
        else s.insert(make_pair(y, z));
      }
    }
  }

  return ret;
}

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> st_x >> st_y >> ed_x >> ed_y;
  cin >> n;

  for(int i = 1; i <= n; i++) cin >> rect[i].x1 >> rect[i].x2 >> rect[i].y1 >> rect[i].y2;

  rect[0].x1 = st_x; rect[0].y1 = st_y;
  rect[0].x2 = ed_x; rect[0].y2 = ed_y;

  for(int i = 0; i <= n; i++) {
    rrhx.push_back(rect[i].x1);
    rrhx.push_back(rect[i].x2);
    rrhy.push_back(rect[i].y1);
    rrhy.push_back(rect[i].y2);
  }

  sort(all(rrhx));
  rrhx.resize(unique(all(rrhx)) - rrhx.begin());
  sort(all(rrhy));
  rrhy.resize(unique(all(rrhy)) - rrhy.begin());

  m = max(rrhx.size(), rrhy.size());

  for(int i = 0; i <= n; i++) {
    rect[i].x1 = upper_bound(all(rrhx), rect[i].x1) - rrhx.begin();
    rect[i].x2 = upper_bound(all(rrhx), rect[i].x2) - rrhx.begin();
    rect[i].y1 = upper_bound(all(rrhy), rect[i].y1) - rrhy.begin();
    rect[i].y2 = upper_bound(all(rrhy), rect[i].y2) - rrhy.begin();
  }
  st_x = rect[0].x1; st_y = rect[0].y1;
  ed_x = rect[0].x2; ed_y = rect[0].y2;

//  cout << st_x << " " << st_y << " " << ed_x << " " << ed_y << endl;
//  for(int i = 1; i <= n; i++) {
//    cout << rect[i].x1 << " " << rect[i].x2 << " " << rect[i].y1 << " " << rect[i].y2 << endl;
//  }

  vector<pair<int, int> > tmp;
  tmp.emplace_back(st_x, st_y);
  tmp.emplace_back(ed_x, ed_y);
  for(int i = 1; i <= n; i++) {
    tmp.emplace_back(rect[i].x1, rect[i].y1);
    tmp.emplace_back(rect[i].x2, rect[i].y2);
  }
  vector<tuple<int, int, int> > line1 = expand(tmp);

  for(auto &[x, y] : tmp) swap(x, y);
  for(int i = 1; i <= n; i++) {
    swap(rect[i].x1, rect[i].y1);
    swap(rect[i].x2, rect[i].y2);
  }

  vector<tuple<int, int, int> > line2 = expand(tmp);

  for(int i = 1; i <= n; i++) {
    swap(rect[i].x1, rect[i].y1);
    swap(rect[i].x2, rect[i].y2);
  }

  int cnt = 0;
  for(auto &[x, y1, y2] : line1) {
    line[++cnt] = {x, y1, y2};
//    cout << x << " " << y1 << " " << y2 << endl;
    if (st_x == x && y1 <= st_y && st_y <= y2) {
      d[cnt] = 1;
      q.push(cnt);
    }
    else itx.up(1, 1, m, y1, y2, make_pair(x, cnt));
  }
  int cntx = cnt;

  for(auto &[y, x1, x2] : line2) {
    line[++cnt] = {y, x1, x2};
//    cout << y << " " << x1 << " " << x2 << endl;
    if (st_y == y && x1 <= st_x && st_x <= x2) {
      d[cnt] = 1;
      q.push(cnt);
    }
    else ity.up(1, 1, m, x1, x2, make_pair(y, cnt));
  }
//  exit(0);

  while (!q.empty()) {
    int u = q.front(); q.pop();
    if (u <= cntx) {
      int x, y1, y2; tie(x, y1, y2) = line[u];
      if (ed_x == x && y1 <= ed_y && ed_y <= y2) return cout << d[u], 0;
      ity.get(1, 1, m, x, y1, y2, d[u] + 1);
    }
    else {
      int y, x1, x2; tie(y, x1, x2) = line[u];
      if (ed_y == y && x1 <= ed_x && ed_x <= x2) return cout << d[u], 0;
      itx.get(1, 1, m, y, x1, x2, d[u] + 1);
    }
  }
}

Compilation message (stderr)

golf.cpp: In member function 'void IT::up(int, int, int, int, int, std::pair<int, int>)':
golf.cpp:26:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int mid = l + r >> 1;
      |               ~~^~~
golf.cpp: In member function 'void IT::get(int, int, int, int, int, int, int)':
golf.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int mid = l + r >> 1;
      |               ~~^~~
golf.cpp: In function 'int32_t main()':
golf.cpp:109:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:110:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:114:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:115:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70