oj.uz

Submission #923132

# Submission time Handle Problem Language Result Execution time Memory
923132 2024-02-06T17:44:00 Z myst6 trapezoid (balkan11_trapezoid) C++14
46 / 100
 490 ms 65536 KB 
#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 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;
  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
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Partially correct 1 ms 604 KB Partially correct
4 Partially correct 2 ms 856 KB Partially correct
5 Partially correct 6 ms 1852 KB Partially correct
6 Partially correct 10 ms 2456 KB Partially correct
7 Partially correct 9 ms 2200 KB Partially correct
8 Partially correct 16 ms 3348 KB Partially correct
9 Partially correct 42 ms 7624 KB Partially correct
10 Partially correct 56 ms 8872 KB Partially correct
11 Partially correct 95 ms 17412 KB Partially correct
12 Partially correct 248 ms 36332 KB Partially correct
13 Partially correct 280 ms 40696 KB Partially correct
14 Partially correct 316 ms 50872 KB Partially correct
15 Partially correct 345 ms 45884 KB Partially correct
16 Partially correct 414 ms 50148 KB Partially correct
17 Partially correct 424 ms 58032 KB Partially correct
18 Partially correct 275 ms 39720 KB Partially correct
19 Partially correct 452 ms 65536 KB Partially correct
20 Partially correct 490 ms 65536 KB Partially correct