結果

問題 No.2796 Small Matryoshka
ユーザー IceKnight1093IceKnight1093
提出日時 2024-06-29 12:23:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,521 bytes
コンパイル時間 2,598 ms
コンパイル使用メモリ 216,540 KB
実行使用メモリ 367,616 KB
最終ジャッジ日時 2024-06-29 12:23:34
合計ジャッジ時間 9,492 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 WA -
testcase_05 AC 131 ms
78,336 KB
testcase_06 AC 657 ms
367,616 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 364 ms
169,984 KB
testcase_09 AC 579 ms
270,464 KB
testcase_10 AC 618 ms
253,952 KB
testcase_11 AC 708 ms
299,648 KB
testcase_12 WA -
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 -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

struct Node {
	using T = int;
	T unit = 0;
	T f(T a, T b) { return max(a, b); }
 
	Node *l = 0, *r = 0;
	int lo, hi;
	T mset = 0;
	T val = unit;
	Node(int _lo,int _hi):lo(_lo),hi(_hi){}
	T query(int L, int R) {
		if (R <= lo || hi <= L) return unit;
		if (L <= lo && hi <= R) return val;
		push();
		return f(l->query(L, R), r->query(L, R));
	}
	void set(int L, int R, T x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) {
			mset = x;
			val = x;
		}
		else {
			push(), l->set(L, R, x), r->set(L, R, x);
			val = f(l->val, r->val);
		}
	}
	void push() {
		if (!l) {
			int mid = lo + (hi - lo)/2;
			l = new Node(lo, mid); r = new Node(mid, hi);
		}
		if (mset)
			l->set(lo,hi,mset), r->set(lo,hi,mset), mset = 0;
	}
};

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int n; cin >> n;
    vector<array<int, 2>> a(n);
    for (auto &[x,y] : a) cin >> x >> y;
    sort(begin(a), end(a), [&] (auto x, auto y) {return x[1] < y[1];});

    Node *seg = new Node(0, 1'000'000'007);
    int ans = 0;
    for (auto [l, r] : a) {
        int best = seg -> query(0, l+1);
        ans = max(ans, best + 1);
        
        int cur = seg -> query(r, r+1);
        if (best + 1 > cur) seg -> set(r, r+1, best + 1);
    }
    cout << n - ans << '\n';
}
0