結果

問題 No.1703 Much Matching
コンテスト
ユーザー tnakao0123
提出日時 2021-10-09 02:24:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,733 bytes
コンパイル時間 321 ms
コンパイル使用メモリ 45,260 KB
実行使用メモリ 26,212 KB
最終ジャッジ日時 2024-07-23 11:53:51
合計ジャッジ時間 4,416 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 3 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 1703.cc:  No.1703 Much Matching - yukicoder
 */

#include<cstdio>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 1000;
const int MAX_M = 1000;
const int MAX_Q = MAX_N * MAX_M;
const int MAX_E2 = 1 << 11; // = 2048

/* typedef */

typedef long long ll;

template <typename T, const int MAX_E2>
struct SegTreeMax2D {
  int e2;
  T nodes[MAX_E2][MAX_E2], minf;
  SegTreeMax2D() {}

  void init(int n, T _minf) {
    minf = _minf;
    for (e2 = 1; e2 < n; e2 <<= 1);
    for (int i = 0; i < e2 * 2; i++)
      fill(nodes[i], nodes[i] + MAX_E2, minf);
  }

  T &geti(int i0, int i1) { return nodes[e2 - 1 + i0][e2 - 1 + i1]; }

  void setall() {
    for (int j0 = e2 - 2; j0 >= 0; j0--) {
      int k00 = j0 * 2 + 1, k01 = k00 + 1;
      for (int j1 = e2 - 2; j1 >= 0; j1--) {
        int k10 = j1 * 2 + 1, k11 = k10 + 1;
        nodes[j0][j1] =
          max(max(nodes[k00][k10], nodes[k00][k11]),
              max(nodes[k01][k10], nodes[k01][k11]));
      }
    }
  }

  void set(int i0, int i1, T v) {
    int j0 = e2 - 1 + i0, j1 = e2 - 1 + i1;
    nodes[j0][j1] = v;
    while (j0 > 0 || j1 > 0) {
      j0 = (j0 - 1) / 2, j1 = (j1 - 1) / 2;
      int k00 = j0 * 2 + 1, k01 = k00 + 1;
      int k10 = j1 * 2 + 1, k11 = k10 + 1;
      nodes[j0][j1] =
        max(max(nodes[k00][k10], nodes[k00][k11]),
            max(nodes[k01][k10], nodes[k01][k11]));
    }
  }

  T max_range(int r00, int r01, int r10, int r11,
              int k0, int k1, int i00, int i01, int i10, int i11) {
    if (r01 <= i00 || i01 <= r00 || r11 <= i10 || i11 <= r10)
      return minf;
    if (r00 <= i00 && i01 <= r01 && r10 <= i10 && i11 <= r11)
      return nodes[k0][k1];

    int im0 = (i00 + i01) / 2, im1 = (i10 + i11) / 2;
    int k00 = k0 * 2 + 1, k01 = k00 + 1;
    int k10 = k1 * 2 + 1, k11 = k10 + 1;

    T v00 = max_range(r00, r01, r10, r11, k00, k10, i00, im0, i10, im1);
    T v01 = max_range(r00, r01, r10, r11, k00, k11, i00, im0, im1, i11);
    T v10 = max_range(r00, r01, r10, r11, k01, k10, im0, i01, i10, im1);
    T v11 = max_range(r00, r01, r10, r11, k01, k11, im0, i01, im1, i11);
    return max(max(v00, v01), max(v10, v11));
  }
  T max_range(int r00, int r01, int r10, int r11) {
    return max_range(r00, r01, r10, r11, 0, 0, 0, e2, 0, e2);
  }
};

/* global variables */

SegTreeMax2D<int,MAX_E2> st;

/* subroutines */

/* main */

int main() {
  int n, m, q;
  scanf("%d%d%d", &n, &m, &q);

  st.init(max(n, m), 0);

  int maxd = 0;
  for (int i = 0; i < q; i++) {
    int ai, bi;
    scanf("%d%d", &ai, &bi);
    ai--, bi--;

    int d = st.max_range(0, ai, 0, bi) + 1;
    st.set(ai, bi, d);
    maxd = max(maxd, d);
  }

  printf("%d\n", maxd);
  return 0;
}
0