oj.uz

답안 #923136

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923136 2024-02-06T17:47:59 Z myst6 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 431 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

const int mod = 30013;

struct Info {
  int m, ct;
  Info(int M, int C) : m(M), ct(C%mod) {}
  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
  cin.tie(0)->sync_with_stdio(0);
  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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 6 ms 1852 KB Output is correct
6 Correct 8 ms 2456 KB Output is correct
7 Correct 8 ms 2200 KB Output is correct
8 Correct 18 ms 3364 KB Output is correct
9 Correct 32 ms 7372 KB Output is correct
10 Correct 45 ms 8664 KB Output is correct
11 Correct 90 ms 17860 KB Output is correct
12 Correct 190 ms 35512 KB Output is correct
13 Correct 232 ms 40880 KB Output is correct
14 Correct 293 ms 50956 KB Output is correct
15 Correct 314 ms 45760 KB Output is correct
16 Correct 352 ms 49036 KB Output is correct
17 Correct 375 ms 58532 KB Output is correct
18 Correct 232 ms 39008 KB Output is correct
19 Correct 372 ms 62384 KB Output is correct
20 Correct 431 ms 65536 KB Output is correct