読者です 読者をやめる 読者になる 読者になる

Codeforces #160 Div1 D. Maxim and Increasing Subsequence

蟻本のアルゴリズムを写経したら通ってしまった…

5304/6000msなのでどう考えても嘘解法
しかもテストケースが甘いからっぽい…N=10^6 MAX_B=200 T=199みたいなので簡単に落とせるハズ
O(K*N*MAX_B*log(N))のはず

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int INT_INF = (1U<<31)-10;

const int MAX_B = 100010, MAX_N = 100010;
int b[MAX_N];
int dp[MAX_N];
set<int> s;
int main(int argc, char *argv[]) {
    int K, N, maxb, T;
    cin >> K >> N >> maxb >> T;
    for (int k = 0; k < K; k++) {
        s.clear();
        for (int i = 0; i < N; i++) {
            scanf("%d", &(b[i]));
            s.insert(b[i]);
        }
        if (T >= s.size()) {
            printf("%ld\n", s.size());
            continue;
        }
        fill(dp, dp+MAX_N, INT_INF);
        for (int i = 0; i < T; i++) {
            for (int j = 0; j < N; j++) {
                if (b[j] < i) continue;
                *lower_bound(dp, dp+N, b[j]) = b[j];
            }
        }
        printf("%ld\n", lower_bound(dp, dp+N, INT_INF) - dp);
    }
    return 0;
}

O(K*N*MAX_B*log(MAX_B))のアルゴリズムがRMQで書けるのでNとMAX_Bを比べて使い分ければいいのかな〜〜と思って書いたけど、定数倍が重すぎて死
サンプル見ながら調整したら3650msになったけどなんだかな〜〜〜と

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int INT_INF = (1U<<31)-10000;

const int MAX_N = 100010;
int K, N, MAX_B, T;
int b[MAX_N], b_num;
int dp[MAX_N];
set<int> s;

int solve_smallN() {
    fill(dp, dp+MAX_N, INT_INF);
    for (int i = 0; i < T; i++) {
        for (int j = 0; j < N; j++) {
            if (b[j] < i) continue;
            *lower_bound(dp, dp+N, b[j]) = b[j];
        }
    }
    return (lower_bound(dp, dp+N, INT_INF) - dp);  
}

const int SEG_SIZE_MAX = 100010*4;
int SEG_SIZE;
int seg[SEG_SIZE_MAX];

void seg_init() {
    SEG_SIZE = 1;
    while (SEG_SIZE < MAX_B) SEG_SIZE *= 2;
    SEG_SIZE *= 2;
    fill(seg, seg+SEG_SIZE, INT_INF);
}

void seg_set(int i, int x) {
    i += SEG_SIZE/2 - 1;
    seg[i] = x;
    while (i) {
        i = (i - 1) / 2;
        int s1 = seg[i*2+1], s2 = seg[i*2+2];
        seg[i] = min(s1, s2);
    }
}

int seg_get(int a, int b, int k = 0, int l = 0, int r = SEG_SIZE/2) {
    if (a <= l && r <= b) return seg[k];
    if (r <= a || b <= l) return INT_INF;
    int vl = seg_get(a, b, k*2+1, l, (l+r)/2);
    int vr = seg_get(a, b, k*2+2, (l+r)/2, r);
    return min(vl, vr);
}

int solve_smallB() {
    seg_init();
    int min_d = 0;
    for (int i = 0; i < T; i++) {
        for (int j = 0; j < N; j++) {
            int d = b[j];
            if (d < min_d) continue;
            int r = seg_get(0, d) - 1;
            if (INT_INF - r == d+1) min_d = max(min_d, d);
            seg_set(d, r);
        }
    }
    return INT_INF - seg_get(0, MAX_B);
}

int main(int argc, char *argv[]) {
    cin >> K >> N >> MAX_B >> T;
    for (int k = 0; k < K; k++) {
        s.clear();
        for (int i = 0; i < N; i++) {
            scanf("%d", &(b[i]));
            b[i]--;
            s.insert(b[i]);
        }
        b_num = s.size();
        if (T >= b_num) {
            printf("%d\n", b_num);
            continue;
        }
        int result;
        if (MAX_B*2 > N) {
            result = solve_smallN();
        } else {
            result = solve_smallB();
        }
        printf("%d\n", result);
    }
    return 0;
}

追記
他人のソースを読んだところ二部探索のするべき範囲をキャッシュして云々すると早くなります