結果

問題 No.686 Uncertain LIS
ユーザー shadowYYHshadowYYH
提出日時 2023-12-25 09:26:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,314 bytes
コンパイル時間 1,867 ms
コンパイル使用メモリ 169,820 KB
実行使用メモリ 27,980 KB
最終ジャッジ日時 2024-09-27 14:14:53
合計ジャッジ時間 4,740 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
23,884 KB
testcase_01 AC 10 ms
21,708 KB
testcase_02 AC 10 ms
23,880 KB
testcase_03 AC 11 ms
23,884 KB
testcase_04 AC 9 ms
21,840 KB
testcase_05 AC 10 ms
23,756 KB
testcase_06 AC 11 ms
21,964 KB
testcase_07 AC 11 ms
23,884 KB
testcase_08 AC 11 ms
23,760 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 11 ms
23,760 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 46 ms
21,708 KB
testcase_25 AC 45 ms
23,756 KB
testcase_26 AC 32 ms
23,884 KB
testcase_27 WA -
testcase_28 AC 45 ms
23,888 KB
testcase_29 AC 48 ms
25,936 KB
testcase_30 WA -
testcase_31 AC 11 ms
23,884 KB
testcase_32 AC 30 ms
23,884 KB
testcase_33 AC 31 ms
23,884 KB
testcase_34 WA -
testcase_35 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define For(x, y, z) for (int x = y, x##E = z; x <= x##E; ++x)
#define Rof(x, y, z) for (int x = y, x##E = z; x >= x##E; --x)
#define Eor(u) for (int i = head[u]; i; i = nxt[i])
#define SZ(x) (int(x.size()))
#define pb push_back

using namespace std;
using i64 = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

// char buf[(1<<21)+5],*p1,*p2;
// #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return f ? -x : x;
}
int __stk[128], __tp;
inline void put(i64 x) {
	if (x < 0) putchar('-'), x = -x;
	do { __stk[++__tp] = x % 10, x /= 10; } while (x);
	while (__tp) putchar(__stk[__tp--] + '0');
}

const int mod = 998244353;
inline int ksm(int x, int y, int res = 1) {
	for ( ; y; y >>= 1, x = 1ll * x * x % mod)
		(y & 1) && (res = 1ll * res * x % mod);
	return res;
}
inline int inv(int x) { return ksm(x, mod - 2); }
inline int gcd(int a, int b) { if (b) while ((a %= b) && (b %= a)); return a | b; }
inline void add(int &x, int y) { (x += y) >= mod && (x -= mod); }
inline void Min(int &x, int y) { (y < x) && (x = y); }
inline void Max(int &x, int y) { (y > x) && (x = y); }

const int N = 2e6 + 1000;

struct BIT{
    int t[N], n, lg; void init(int nn) { For(i, 0, n = nn) t[i] = 0; lg = log2(n); }
    void Add(int x, int y) { for (; x <= n; x += x & -x) t[x] += y; }
    int operator[](int x){ int y = 0; for (; x; x -= x & -x) y += t[x]; return y; }
    int find(int v) {
        int p = 0, sum = 0; Rof(i, lg, 0) if ((p | (1 << i)) <= n 
        && sum + t[p | (1 << i)] <= v) p |= 1 << i, sum += t[p]; return p;
    }
}f, pos;
int n, L[N], R[N], p[N];

signed main() {
	// freopen("lis.in", "r", stdin);
	// freopen("lis.out", "w", stdout);

    n = read(), f.init(1e6 + n + 2), pos.init(1e6);
    For(i, 1, n) L[i] = read(), R[i] = read(), ++p[max(L[i] - 1, 1)];
    For(i, 1, 1e6) p[i] += p[i - 1] + 1;
    
    For(i, 1, n) {
        pos.Add(max(L[i] - 1, 1), 1), pos.Add(R[i] + 1, -1);
        int l = p[L[i]] - pos[L[i]], r = p[R[i]] - pos[R[i]];
        f.Add(l, 1), f.Add(f.find(f[r]) + 1, -1);
    }
    
	cout << f[1e6];
	return 0;
}
0