Submission #499189

#	Time	Username	Problem	Language	Result	Execution time	Memory
499189		600Mihnea	Golf (JOI17_golf)	C++17	30 / 100	10093 ms	89836 KiB

golf

#include <bits/stdc++.h>

using namespace std;

#define y1 ynot1

typedef long long ll;
typedef long double ld;

struct Box {
  int xmin;
  int xmax;
  int ymin;
  int ymax;

};

const int N = 100000 + 7;
const int INF = (int) 1e9 + 7;

int n;
int x1;
int y1;
int x2;
int y2;
Box boxes[N];

void normalization() {
  map<int, int> mx, my;

  for (int i = 0; i <= n + 1; i++) {
    mx[boxes[i].xmin] = 0;
    mx[boxes[i].xmax] = 0;

    my[boxes[i].ymin] = 0;
    my[boxes[i].ymax] = 0;
  }

  int c = 0;
  for (auto &it : mx) {
    it.second = ++c;
  }

  c = 0;
  for (auto &it : my) {
    it.second = ++c;
  }


  for (int i = 0; i <= n + 1; i++) {
    boxes[i].xmin = mx[boxes[i].xmin];
    boxes[i].xmax = mx[boxes[i].xmax];

    boxes[i].ymin = my[boxes[i].ymin];
    boxes[i].ymax = my[boxes[i].ymax];
  }
}

struct Segment {
  int where;
  int low;
  int high;
  int e_low;
  int e_high;
  int dp;
};

/**

segment tree of lasts

**/

struct Node {
  int mn;
  int mx;
};

Node operator + (Node a, Node b) {
  return {min(a.mn, b.mn), max(a.mx, b.mx)};
}

const Node non = {2 * N, 0};
Node segt1[8 * N];
Node lazy1[8 * N];

void push(int v, int tl, int tr) {
  if (lazy1[v].mn == non.mn && lazy1[v].mx == non.mx) {
    return;
  }

  segt1[v] = segt1[v] + lazy1[v];

  if (tl < tr) {
    lazy1[2 * v] = lazy1[2 * v] + lazy1[v];
    lazy1[2 * v + 1] = lazy1[2 * v + 1] + lazy1[v];
  }

  lazy1[v] = non;
}

void updsegt1(int v, int tl, int tr, int l, int r, int x) {
  push(v, tl, tr);
  if (tr < l || r < tl) {
    return;
  }
  if (l <= tl && tr <= r) {
    lazy1[v] = lazy1[v] + Node{x, x};
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  updsegt1(2 * v, tl, tm, l, r, x);
  updsegt1(2 * v + 1, tm + 1, tr, l, r, x);
  segt1[v] = segt1[2 * v] + segt1[2 * v + 1];
}

void updsegt1(int l, int r, int x) {
  if (l > r) {
    return;
  }
  assert(1 <= l && l <= r && r <= 2 * (n + 2));
  updsegt1(1, 1, 2 * (n + 2), l, r, x);
}

Node getsegt1(int v, int tl, int tr, int l, int r) {
  push(v, tl, tr);
  if (tr < l || r < tl) {
    return non;
  }
  if (l <= tl && tr <= r) {
    return segt1[v];
  }
  int tm = (tl + tr) / 2;
  return getsegt1(2 * v, tl, tm, l, r) + getsegt1(2 * v + 1, tm + 1, tr, l, r);
}

Node getsegt1(int l, int r) {
  return getsegt1(1, 1, 2 * (n + 2), l, r);
}

void clr() {
  for (int i = 0; i < 8 * N; i++) {
    segt1[i] = non;
    lazy1[i] = non;
  }
}


vector<vector<Segment>> segs;
vector<Segment> xSegs;
vector<Segment> ySegs;

bool cmpextlowX(int i, int j) {
  return xSegs[i].low < xSegs[j].low;
}

bool cmpexthighX(int i, int j) {
  return xSegs[i].high > xSegs[j].high;
}

bool cmpextY(int i, int j) {
  return ySegs[i].where < ySegs[j].where;
}

bool cmp(int i, int j) {
  return xSegs[i].e_low < xSegs[j].e_low;
}

void calculateextensions() {

  for (int step = 1; step <= 2; step++) {
    /// calculate x segs
    for (int i = 0; i <= n + 1; i++) {
      xSegs.push_back({boxes[i].ymin, boxes[i].xmin, boxes[i].xmax, 0, 2 * N, -1});
      xSegs.push_back({boxes[i].ymax, boxes[i].xmin, boxes[i].xmax, 0, 2 * N, -1});
    }

    for (int i = 0; i <= n + 1; i++) {
      swap(boxes[i].xmin, boxes[i].ymin);
      swap(boxes[i].xmax, boxes[i].ymax);
    }

    swap(xSegs, ySegs);
  }

  assert((int) xSegs.size() == 2 * (n + 2));
  assert((int) ySegs.size() == 2 * (n + 2));

  for (int step = 1; step <= 2; step++) {
    /// compute the extensions

    {
      vector<int> ordx(2 * (n + 2)), ordy;
      iota(ordx.begin(), ordx.end(), 0);
      ordy = ordx;
      sort(ordx.begin(), ordx.end(), cmpextlowX);
      sort(ordy.begin(), ordy.end(), cmpextY);

      {
        clr();
        int ptr = 0;
        for (int it = 0; it < 2 * (n + 2); it++) {
          int i = ordx[it];


          while (ptr < 2 * (n + 2) && ySegs[ordy[ptr]].where < xSegs[i].low) {
            updsegt1(ySegs[ordy[ptr]].low + 1, ySegs[ordy[ptr]].high - 1, ySegs[ordy[ptr]].where);
            ptr++;
          }

          xSegs[i].e_low = getsegt1(xSegs[i].where, xSegs[i].where).mx;
        }
      }

      {
        reverse(ordx.begin(), ordx.end()); /// optimization, daca nu merge, incearca cmpexthighX
        reverse(ordy.begin(), ordy.end());

        clr();
        int ptr = 0;
        for (int it = 0; it < 2 * (n + 2); it++) {
          int i = ordx[it];


          while (ptr < 2 * (n + 2) && ySegs[ordy[ptr]].where > xSegs[i].high) {
            updsegt1(ySegs[ordy[ptr]].low + 1, ySegs[ordy[ptr]].high - 1, ySegs[ordy[ptr]].where);
            ptr++;
          }

          xSegs[i].e_high = getsegt1(xSegs[i].where, xSegs[i].where).mn;
        }
      }

    }


    /// checker

    for (auto &it : xSegs) {
      assert(it.e_low <= it.low);
      assert(it.high <= it.e_high);
    }

    swap(xSegs, ySegs);
  }
  segs.push_back(xSegs);
  segs.push_back(ySegs);
}

queue<pair<int, int>> q;
bool deja[2][2 * N];

void addToQ(int type, int index, int value) {
  deja[type][index] = 1;
  assert(0 <= type && type < 2);
  assert(0 <= index && index < (int) segs[type].size());
  assert(segs[type][index].dp == -1);
  segs[type][index].dp = value;
  q.push({type, index});
}

struct Snode {
  int index;
  int l;
  int r;
};

bool operator < (Snode a, Snode b) {
  if (a.l != b.l) {
    return a.l < b.l;
  }
  return a.index < b.index;
}

set<Snode> guys[2][2 * N];
int cnt[2][8 * N];
vector<int> now;

set<int> ct;

void addToSegt(int type, int v, int tl, int tr, int i, Snode node) {
  if (tr < i || i < tl) {
    return;
  }
  if (tl == tr) {
    guys[type][tl].insert(node);
    assert(!ct.count(node.index));
    ct.insert(node.index);

    cnt[type][v] = (int) guys[type][tl].size();
    return;
  }
  int tm = (tl + tr) / 2;
  addToSegt(type, 2 * v, tl, tm, i, node);
  addToSegt(type, 2 * v + 1, tm + 1, tr, i, node);
  cnt[type][v] = cnt[type][2 * v] + cnt[type][2 * v + 1];
}

void del(int type, int v, int tl, int tr, int l, int r, int i) {
  if (cnt[type][v] == 0) {
    return;
  }
  if (tr < l || r < tl) {
    return;
  }
  if (tl == tr) {
    while (!guys[type][tl].empty()) {
      auto it = guys[type][tl].begin();
      if (it->l <= i && it->r >= i) {
        if (!deja[type][it->index]) now.push_back(it->index);
        guys[type][tl].erase(it);
      } else {
        break;
      }
    }
    while (!guys[type][tl].empty()) {
      auto it = guys[type][tl].lower_bound({-1, i + 1, -1});
      if (it == guys[type][tl].begin()) {
        break;
      }
      it--;
      assert(it->l <= i);
      if (it->l <= i && it->r >= i) {
        if (!deja[type][it->index]) now.push_back(it->index);
        guys[type][tl].erase(it);
      } else {
        break;
      }
    }
    cnt[type][v] = (int) guys[type][tl].size();
    return;
  }
  int tm = (tl + tr) / 2;
  del(type, 2 * v, tl, tm, l, r, i);
  del(type, 2 * v + 1, tm + 1, tr, l, r, i);
  cnt[type][v] = cnt[type][2 * v] + cnt[type][2 * v + 1];
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  ///freopen ("input", "r", stdin);

  cin >> x1 >> y1 >> x2 >> y2;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> boxes[i].xmin >> boxes[i].xmax >> boxes[i].ymin >> boxes[i].ymax;
  }

  boxes[0].xmin = boxes[0].xmax = x1;
  boxes[0].ymin = boxes[0].ymax = y1;

  boxes[n + 1].xmin = boxes[n + 1].xmax = x2;
  boxes[n + 1].ymin = boxes[n + 1].ymax = y2;

  normalization(); /// do it later

  calculateextensions();


  if (n > 1000) {
    /// exit(0); /// I wanted to measure the first part of the algorithm
  }

  addToQ(0, 0, 1);
  addToQ(0, 1, 1);
  addToQ(1, 0, 1);
  addToQ(1, 1, 1);

  /*for (int type = 0; type < 2; type++) {
    xSegs = segs[type];
    vector<int> inds(2 * (n + 2));
    iota(inds.begin(), inds.end(), 0);
   /// assert((int) inds.size() == (int) xSegs.size());
   // continue;
    sort(inds.begin(), inds.end(), cmp);
    map<int, int> last;
    for (auto &it : inds) {
      assert(last[xSegs[it].where] <= xSegs[it].e_high);
      last[xSegs[it].where] = xSegs[it].e_high;
    }
  }*/
  for (int type = 0; type < 2; type++) {
    for (int i = 0; i < 2 * (n + 2); i++) {
      addToSegt(type, 1, 1, 2 * (n + 2), segs[type][i].where, {i, segs[type][i].e_low, segs[type][i].e_high});
    }
    ct.clear();
  }


  while (!q.empty()) {
    auto itQ = q.front();
    q.pop();
    int type = itQ.first;
    int index = itQ.second;


    int dp = segs[type][index].dp;

    assert(2 * (n + 2) == (int) segs[type ^ 1].size());

    now.clear();
    del(type ^ 1, 1, 1, 2 * (n + 2), segs[type][index].e_low, segs[type][index].e_high, segs[type][index].where);


    vector<int> scNow;

    for (int j = 0; j < 2 * (n + 2); j++) {
      if (segs[type ^ 1][j].dp == -1
          && segs[type ^ 1][j].e_low <= segs[type][index].where && segs[type][index].where <= segs[type ^ 1][j].e_high
          && segs[type][index].e_low <= segs[type ^ 1][j].where && segs[type ^ 1][j].where <= segs[type][index].e_high) {
        scNow.push_back(j);
        addToQ(type ^ 1, j, segs[type][index].dp + 1);
      }
    }

    /// void del(int type, int v, int tl, int tr, int l, int r, int i)


    sort(scNow.begin(), scNow.end());
    sort(now.begin(), now.end());
    assert(now == scNow);
    continue;
    if (!scNow.empty()) {
      cout << "a : ";
      for (auto &it : scNow) cout << it << " ";
      cout << "\n";
    }
    if (!now.empty()) {
      cout << "b : ";
      for (auto &it : now) cout << it << " ";
      cout << "\n";
    }
    if ((int) scNow.size() + (int) now.size() > 0) {
      cout << "\n";
    }
  }

  for (auto &v : segs) {
    for (auto &seg : v) {
      assert(seg.dp != -1);
    }
  }

  x2 = boxes[n + 1].xmin;
  y2 = boxes[n + 1].ymin;

  int sol = INF;

  swap(x2, y2);

  for (auto &v : segs) {
    for (auto &seg : v) {
      if (x2 == seg.where && seg.e_low <= y2 && y2 <= seg.e_high) {
        sol = min(sol, seg.dp);
      }
    }
    swap(x2, y2);
  }

  cout << sol << "\n";


  return 0;
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:399:9: warning: unused variable 'dp' [-Wunused-variable]
  399 |     int dp = segs[type][index].dp;
      |         ^~

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