oj.uz

답안 #334829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
334829 2020-12-10T04:35:48 Z VROOM_VARUN 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 351 ms 45396 KB 
/*
ID: varunra2
LANG: C++
TASK: trapezoids
*/

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 30013
#define MOD1 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

int n;
VVI vals;
MPII cmp;
VI dp1;
VI dp2;

int siz;

void compress(VI& use) {
  sort(all(use));
  use.resize(unique(all(use)) - use.begin());
  rep(i, 0, sz(use)) cmp[use[i]] = i;
  siz = sz(use);
}

void init() {
  vals.resize(n);
  dp1.resize(n);
  dp2.resize(n);
}

void upd(PII& cur, PII& nw) {
  if (nw.x > cur.x)
    cur = nw;
  else if (nw.x == cur.x)
    cur.y += nw.y;
}

PII comb(PII a, PII b) {
  if (a.x > b.x) return a;
  if (b.x > a.x) return b;
  return MP(a.x, (a.y + b.y) % MOD);
}

const PII bad(0, 0);

struct segtree {
  int n;
  VII st;

  void init(int _n) {
    n = _n;
    st.assign(4 * n, bad);
  }

  PII qry(int tl, int tr, int l, int r, int node) {
    if (l > r) return bad;
    if (tl > r or tr < l) return bad;
    if (tl <= l and tr >= r) return st[node];
    int mid = (l + r) / 2;
    return comb(qry(tl, tr, l, mid, 2 * node + 1),
                qry(tl, tr, mid + 1, r, 2 * node + 2));
  }

  void upd(int ind, PII val, int l, int r, int node) {
    if (ind < l or ind > r) return;
    if (ind == l and ind == r) {
      ::upd(st[node], val);
      return;
    }
    int mid = (l + r) / 2;
    upd(ind, val, l, mid, 2 * node + 1);
    upd(ind, val, mid + 1, r, 2 * node + 2);
    st[node] = comb(st[2 * node + 1], st[2 * node + 2]);
  }

  PII qry(int l, int r) {
    auto ret = qry(l, r, 0, n - 1, 0);
    return ret;
  }

  void upd(int ind, int val, int cnt) {
    upd(ind, MP(val, cnt), 0, n - 1, 0);
  }
} st;

int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);

  cin >> n;

  init();

  VI pnts;

  for (int i = 0; i < n; i++) {
    vals[i].resize(4);
    for (int j = 0; j < 4; j++) {
      cin >> vals[i][j];
      pnts.PB(vals[i][j]);
    }
  }

  compress(pnts);

  st.init(siz);

  VVI sweep;

  for (int i = 0; i < n; i++) {
    int a, b, c, d;
    a = vals[i][0], b = vals[i][1], c = vals[i][2], d = vals[i][3];
    sweep.PB({a, c, i, 0});
    sweep.PB({b, d, i, 1});
  }

  sort(all(sweep));

  int ret = -1, cnt = 0;

  trav(x, sweep) {
    int a = x[0];
    int b = x[1];
    int ind = x[2];
    int type = x[3];
    if (type == 0) {
      tie(dp1[ind], dp2[ind]) = st.qry(0, cmp[b]);
      dp1[ind]++;
      if (dp1[ind] == 1) dp2[ind] = 1;
      if (dp1[ind] > ret) ret = dp1[ind], cnt = 0;
      if (dp1[ind] == ret) cnt = (cnt + dp2[ind]) % MOD;
    }
    if (type == 1) {
      st.upd(cmp[b], dp1[ind], dp2[ind]);
    }
  }

  cout << ret << " " << cnt << '\n';

  return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:168:9: warning: unused variable 'a' [-Wunused-variable]
  168 |     int a = x[0];
      |         ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 6 ms 1260 KB Output is correct
6 Correct 8 ms 1900 KB Output is correct
7 Correct 8 ms 1772 KB Output is correct
8 Correct 13 ms 2540 KB Output is correct
9 Correct 29 ms 5284 KB Output is correct
10 Correct 44 ms 7656 KB Output is correct
11 Correct 76 ms 12124 KB Output is correct
12 Correct 165 ms 24536 KB Output is correct
13 Correct 201 ms 28504 KB Output is correct
14 Correct 249 ms 37080 KB Output is correct
15 Correct 257 ms 34776 KB Output is correct
16 Correct 300 ms 36360 KB Output is correct
17 Correct 312 ms 41048 KB Output is correct
18 Correct 213 ms 31712 KB Output is correct
19 Correct 328 ms 43732 KB Output is correct
20 Correct 351 ms 45396 KB Output is correct