oj.uz

Submission #923131

# Submission time Handle Problem Language Result Execution time Memory
923131 2024-02-06T17:41:07 Z myst6 trapezoid (balkan11_trapezoid) C++14
42 / 100
 474 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 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Partially correct 2 ms 604 KB Partially correct
4 Partially correct 3 ms 860 KB Partially correct
5 Partially correct 7 ms 1980 KB Partially correct
6 Partially correct 12 ms 2672 KB Partially correct
7 Partially correct 12 ms 2464 KB Partially correct
8 Partially correct 20 ms 3536 KB Partially correct
9 Partially correct 42 ms 8264 KB Partially correct
10 Partially correct 68 ms 10980 KB Partially correct
11 Partially correct 118 ms 20016 KB Partially correct
12 Partially correct 260 ms 40720 KB Partially correct
13 Partially correct 303 ms 46996 KB Partially correct
14 Partially correct 381 ms 57332 KB Partially correct
15 Partially correct 409 ms 53124 KB Partially correct
16 Partially correct 468 ms 56296 KB Partially correct
17 Partially correct 474 ms 65536 KB Partially correct
18 Partially correct 337 ms 47836 KB Partially correct
19 Runtime error 365 ms 65536 KB Execution killed with signal 9
20 Runtime error 399 ms 65536 KB Execution killed with signal 9