Submission #923131

#	Time	Username	Problem	Language	Result	Execution time	Memory
923131		myst6	trapezoid (balkan11_trapezoid)	C++14	42 / 100	474 ms	65536 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

// one trapezium doesn't overlap with another if and only if a2>b1 and c2>d1
// so at each 'b', add the LIS value on the bottom line 'd'
// and at each 'd', add the LIS value on the top line at 'b'
// then at each 'a', range query the bottom in [1, c-1] and add 1
// and at each 'c', range query for all top in [1, a-1] and add 1

// what about when b < c ?, when updating the LIS, update 
// any values on the top/bottom lines too, if they exist

struct Info {
  int m, ct;
  Info(int M, int C) : m(M), ct(C) {}
  Info() : Info(0, 0) {}
  Info combine(Info &other) {
    if (m == other.m) return {m, ct + other.ct};
    else if (m > other.m) return {m, ct};
    else return {other.m, other.ct};  
  }
};

struct Tree {
  vector<Info> info;
  Tree(int size) { info.resize(size*4); }
  void build(vector<Info> &base, int x, int xl, int xr) {
    if (xl == xr) {
      info[x] = base[xl];
    } else {
      int xm = (xl + xr) / 2;
      build(base, x*2, xl, xm);
      build(base, x*2+1, xm+1, xr);
      info[x] = info[x*2].combine(info[x*2+1]);
    }
  }
  void update(int v, int x, int xl, int xr, Info delta) {
    if (xl == xr) {
      info[x] = delta;
    } else {
      int xm = (xl + xr) / 2;
      if (v <= xm) update(v, x*2, xl, xm, delta);
      else update(v, x*2+1, xm+1, xr, delta);
      info[x] = info[x*2].combine(info[x*2+1]);
    }
  }
  Info query(int l, int r, int x, int xl, int xr) {
    if (l > r) return {};
    assert(xl <= xr);
    if (l == xl && r == xr) {
      return info[x];
    } else {
      int xm = (xl + xr) / 2;
      Info left = query(l, min(r, xm), x*2, xl, xm);
      Info right = query(max(l, xm+1), r, x*2+1, xm+1, xr);
      return left.combine(right);
    }
  }
};

int main() {
  // take inputs // coord compression
  int N;
  cin >> N;
  vector<array<int,4>> shapes(N);
  set<int> coords;
  for (int i=0; i<N; i++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    coords.insert(a); coords.insert(c);
    coords.insert(b); coords.insert(d);
    shapes[i] = {{a, b, c, d}};
  }
  map<int,int> idxmap;
  int L = 0;
  for (int coord : coords) idxmap[coord] = L++;

  // find events
  vector<array<int,5>> events(4*N);
  for (int i=0; i<N; i++) {
    array<int,4> shape = shapes[i];
    events.push_back({shape[0], i, 0, 1, idxmap[shape[2]]-1}); // 0=query,1=bottom
    events.push_back({shape[2], i, 0, 0, idxmap[shape[0]]-1}); // 0=query,0=top
    events.push_back({shape[1], i, 1, 1, idxmap[shape[3]]}); // 1=update,1=bottom
    events.push_back({shape[3], i, 1, 0, idxmap[shape[1]]}); // 1=update,0=top
  }
  sort(events.begin(), events.end());

  // make trees and sweep line
  vector<Info> lisValue(N, {1, 1});
  Tree topTree(L), bottomTree(L);
  vector<int> topPos(N, -1), bottomPos(N, -1);
  for (array<int,5> event : events) {
    if (event[2] == 0) {
      // query
      Info info;
      if (event[3] == 0) info = topTree.query(0, event[4], 1, 0, L-1);
      else info = bottomTree.query(0, event[4], 1, 0, L-1);
      info.m += 1;
      if (info.m == 1) info.ct = 1; // can only start once
      lisValue[event[1]] = info;
    } else {
      // update
      if (event[3] == 0) topPos[event[1]] = event[4];
      else bottomPos[event[1]] = event[4];
    }
    if (topPos[event[1]] != -1) {
      topTree.update(topPos[event[1]], 1, 0, L-1, lisValue[event[1]]);
    }
    if (bottomPos[event[1]] != -1) {
      bottomTree.update(bottomPos[event[1]], 1, 0, L-1, lisValue[event[1]]);
    }
    // cout << "---\n";
    // for (int i=0; i<L; i++) cout << topTree.query(i, i, 1, 0, L-1).m << " "; cout << "\n";
    // for (int i=0; i<L; i++) cout << bottomTree.query(i, i, 1, 0, L-1).m << " "; cout << "\n";
  }

  // get overall answer
  Info all = topTree.query(0, L-1, 1, 0, L-1);
  cout << all.m << " " << all.ct << "\n";

  return 0;
}

• Subtask 1: 42 / 100