oj.uz

답안 #923134

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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 7 ms 1852 KB Output is correct
6 Correct 12 ms 2456 KB Output is correct
7 Correct 10 ms 2196 KB Output is correct
8 Correct 17 ms 3156 KB Output is correct
9 Correct 36 ms 7464 KB Output is correct
10 Correct 56 ms 8908 KB Output is correct
11 Correct 100 ms 17372 KB Output is correct
12 Correct 271 ms 35300 KB Output is correct
13 Correct 290 ms 40628 KB Output is correct
14 Correct 335 ms 51448 KB Output is correct
15 Correct 356 ms 46004 KB Output is correct
16 Correct 393 ms 49072 KB Output is correct
17 Correct 446 ms 58860 KB Output is correct
18 Correct 301 ms 39904 KB Output is correct
19 Correct 440 ms 63544 KB Output is correct
20 Execution timed out 519 ms 65536 KB Time limit exceeded