結果

問題 No.686 Uncertain LIS
ユーザー konjakujellykonjakujelly
提出日時 2023-12-25 10:57:42
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 434 ms / 2,000 ms
コード長 3,747 bytes
コンパイル時間 1,682 ms
コンパイル使用メモリ 171,104 KB
実行使用メモリ 25,944 KB
最終ジャッジ日時 2023-12-25 10:57:52
合計ジャッジ時間 9,177 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
25,560 KB
testcase_01 AC 13 ms
25,560 KB
testcase_02 AC 13 ms
25,560 KB
testcase_03 AC 14 ms
25,944 KB
testcase_04 AC 14 ms
25,816 KB
testcase_05 AC 14 ms
25,944 KB
testcase_06 AC 13 ms
25,560 KB
testcase_07 AC 13 ms
25,560 KB
testcase_08 AC 13 ms
25,560 KB
testcase_09 AC 359 ms
25,944 KB
testcase_10 AC 355 ms
25,944 KB
testcase_11 AC 227 ms
25,944 KB
testcase_12 AC 23 ms
25,944 KB
testcase_13 AC 127 ms
25,944 KB
testcase_14 AC 77 ms
25,560 KB
testcase_15 AC 55 ms
25,560 KB
testcase_16 AC 122 ms
25,560 KB
testcase_17 AC 434 ms
25,944 KB
testcase_18 AC 431 ms
25,944 KB
testcase_19 AC 425 ms
25,944 KB
testcase_20 AC 156 ms
25,560 KB
testcase_21 AC 157 ms
25,560 KB
testcase_22 AC 54 ms
25,560 KB
testcase_23 AC 55 ms
25,560 KB
testcase_24 AC 221 ms
25,944 KB
testcase_25 AC 214 ms
25,944 KB
testcase_26 AC 47 ms
25,944 KB
testcase_27 AC 258 ms
25,944 KB
testcase_28 AC 261 ms
25,944 KB
testcase_29 AC 264 ms
25,944 KB
testcase_30 AC 262 ms
25,944 KB
testcase_31 AC 13 ms
25,560 KB
testcase_32 AC 48 ms
25,944 KB
testcase_33 AC 47 ms
25,944 KB
testcase_34 AC 419 ms
25,944 KB
testcase_35 AC 428 ms
25,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int findrk(int)':
main.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
   77 | }
      | ^

ソースコード

diff # 

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

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while (ch < '0' or ch > '9') f |= (ch == '-'), ch = getchar();
	while (ch >= '0' and ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

int __stk[128], __top;
inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
	do { __stk[++__top] = x % 10, x /= 10; } while (x);
	while (__top) putchar(__stk[__top--] + '0');
}

const int mod = 998244353;

void Min(int &x, int y) { y < x and (x = y); }
void Max(int &x, int y) { y > x and (x = y); }

void inc(int &x, int y) { (x += y) >= mod and (x -= mod); }
void mul(int &x, int y) { x = 1ll * x * y % mod; }

int q_pow(int x, int k) { int res = 1; for (; k; k >>= 1, mul(x, x)) if (k & 1) mul(res, x); return res; }

bool stmer;

const int N = 1e6 + 10, M = 1e6;

int n, rt, cnt, top;
int t[N][2], fa[N], siz[N], s[N], tag[N], stk[N];

void update(int x) { siz[x] = siz[t[x][0]] + siz[t[x][1]] + 1; }

void pushup(int x, int k) { tag[x] += k, s[x] += k; }
void pushdown(int x) { pushup(t[x][0], tag[x]), pushup(t[x][1], tag[x]), tag[x] = 0; }

int build(int l, int r) {
    if (l > r) return 0; int mid = (l + r) >> 1, x = ++cnt;
    t[x][0] = build(l, mid - 1), t[x][1] = build(mid + 1, r);
    return update(x), fa[t[x][0]] = fa[t[x][1]] = x;
}

int get(int x) { return t[fa[x]][1] == x; }

void rotate(int x) {
    int f1 = fa[x], f2 = fa[f1], k = get(x);
    if (f2) t[f2][get(f1)] = x; fa[x] = f2;
    t[f1][k] = t[x][!k], fa[t[f1][k]] = f1;
    t[x][!k] = f1, fa[f1] = x;
    update(f1), update(x);
}

void splay(int x, int to = 0) {
    if (x == to) return;
    int p = stk[top = 1] = x;
    while (fa[p] ^ to) stk[++top] = p = fa[p];
    while (top) pushdown(stk[top--]);
    for (int f; (f = fa[x]) ^ to; rotate(x)) 
        if (fa[f] ^ to) rotate(get(x) == get(f) ? f : x);
    if (!to) rt = x; 
}

int findrk(int k) {
    int x = rt;
    while (x) {
        pushdown(x);
        if (k <= siz[t[x][0]]) x = t[x][0];
        else {
            k -= siz[t[x][0]] + 1;
            if (!k) return x;
            x = t[x][1];
        }
    }
}

void split(int l, int r) { splay(findrk(l)), splay(findrk(r + 3), rt); }

void out(int x) {
    if (!x) return;
    pushdown(x), out(t[x][0]);
    write(s[x]), putchar(' ');
    out(t[x][1]);
}

bool edmer;
signed main() {
	// freopen("Yukicoder686.in", "r", stdin);
	// freopen("Yukicoder686.out", "w", stdout);
	cerr << "[Memory] " << (&stmer - &edmer) / 1024 / 1024 << " MB\n";
	
    n = read(), rt = build(-1, M + 1);
    
    for (int i = 1; i <= n; i++) {
        int l = read(), r = read(), x, y, z;
        split(l, r), x = y = t[t[rt][1]][0];

        while (t[y][0]) pushdown(y), y = t[y][0];
        int val = s[y];

        while (t[x][1]) pushdown(x), x = t[x][1];
        y = fa[x], z = t[x][0], pushdown(x);

        t[y][y != t[rt][1]] = z, fa[z] = y, update(y);
        splay(z ? z : y, t[rt][1]);

        y = t[t[rt][1]][0], pushup(y, 1);

        while (t[y][0]) pushdown(y), y = t[y][0];
        s[x] = val, tag[x] = 0, pushdown(y);

        t[x][0] = 0, siz[x] = 1, t[y][0] = x, fa[x] = y;
        update(y), splay(x, y = t[rt][1]);

        while (t[x][1]) pushdown(x), x = t[x][1];
        if (s[y] < s[x]) {
            int lat = y;
            s[y]++, pushdown(y), y = t[y][1];
            while (y) {
                lat = y, pushdown(y);
                if (s[y] >= s[x]) y = t[y][0];
                else s[y]++, pushup(t[y][0], 1), y = t[y][1];
            }
            splay(lat);
        }
    }

    int x = rt;
    while (t[x][1]) pushdown(x), x = t[x][1];

    write(s[x]);

    cerr << "[Runtime] " << (double) clock() / CLOCKS_PER_SEC << " seconds\n";
	return 0;
}
0