結果
問題 |
No.686 Uncertain LIS
|
ユーザー |
|
提出日時 | 2025-02-24 16:45:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 189 ms / 2,000 ms |
コード長 | 3,475 bytes |
コンパイル時間 | 1,780 ms |
コンパイル使用メモリ | 174,600 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-24 16:45:34 |
合計ジャッジ時間 | 6,923 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include<bits/stdc++.h> #define ls(k) k << 1 #define rs(k) k << 1 | 1 #define fi first #define se second #define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout); using namespace std; typedef __int128 __; typedef long double lb; typedef double db; typedef unsigned long long ull; typedef long long ll; bool Begin; const int N = 1e5 + 10; inline ll read(){ ll x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9'){ if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9'){ x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * f; } inline void write(ll x){ if(x < 0){ putchar('-'); x = -x; } if(x > 9) write(x / 10); putchar(x % 10 + '0'); } int n, l, r; struct Node{ int l, r, val, siz, key; int add; Node(){ l = r = val = siz = 0; add = 0; key = -1; } Node(int x){ l = r = 0; siz = 1; val = x; add = 0; key = rand(); } }; struct FHQ_Treap{ int n, rt; vector<Node> a; FHQ_Treap(){ n = rt = 0; a = vector<Node>(N); } void pushup(int x){ a[x].siz = a[a[x].l].siz + a[a[x].r].siz + 1; } void mktag(int x, int v){ a[x].val += v; a[x].add += v; } void pushdown(int x){ mktag(a[x].l, a[x].add); mktag(a[x].r, a[x].add); a[x].add = 0; } void spt_sz(int x, int k, int &L, int &R){ if (x == 0){ L = R = 0; return; } pushdown(x); if (a[a[x].l].siz + 1 <= k) L = x, spt_sz(a[x].r, k - a[a[x].l].siz - 1, a[x].r, R); else R = x, spt_sz(a[x].l, k, L, a[x].l); pushup(x); } void spt_val(int x, int k, int &L, int &R){ if (x == 0){ L = R = 0; return; } pushdown(x); if (a[x].val < k) L = x, spt_val(a[x].r, k, a[x].r, R); else R = x, spt_val(a[x].l, k, L, a[x].l); pushup(x); } int mrg(int L, int R){ if (L == 0 || R == 0) return L + R; pushdown(L); pushdown(R); if (a[L].key > a[R].key){ a[L].r = mrg(a[L].r, R); pushup(L); return L; } else{ a[R].l = mrg(L, a[R].l); pushup(R); return R; } } int nxt(int v){ int L, M, R, ans; spt_val(rt, v + 1, L, R); spt_sz(R, 1, M, R); if (M == 0) return 0; ans = a[M].val; rt = mrg(L, mrg(M, R)); return ans; } void insert(int v){ int L, M = ++n, R; a[M] = Node(v); spt_val(rt, v, L, R); rt = mrg(L, mrg(M, R)); } void del(int x) { int L, M, R; spt_val(rt, x, L, R); spt_sz(R, 1, M, R); rt = mrg(L, R); } void modify(int l, int r, int v){ int L, M, R; spt_val(rt, l, L, R); spt_val(R, r, M, R); mktag(M, v); rt = mrg(L, mrg(M, R)); } } T; bool End; int main(){ n = read(); for (int i = 1; i <= n; i++){ l = read(), r = read(); if (i == 1){ T.insert(l); continue; } int x = T.nxt(r - 1); T.modify(l, r, 1); if (x) T.del(x); T.insert(l); } write(T.a[T.rt].siz); return 0; }