結果

問題 No.2796 Small Matryoshka
ユーザー IceKnight1093
提出日時 2024-06-29 12:23:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,521 bytes
コンパイル時間 2,680 ms
コンパイル使用メモリ 208,940 KB
最終ジャッジ日時 2025-02-22 01:33:54
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 11
権限があれば一括ダウンロードができます

ソースコード

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