結果

問題 No.711 競技レーティング単調増加
コンテスト
ユーザー minami
提出日時 2018-06-29 23:20:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,264 bytes
コンパイル時間 2,019 ms
コンパイル使用メモリ 184,012 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-07-01 00:15:09
合計ジャッジ時間 5,707 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

struct RangeUpdateQuery {
	int n;
	vector<int> d;
	vector<int> timestamp;
	int time;
	RangeUpdateQuery(int m) {
		for (n = 1; n < m; n *= 2);
		d.assign(n * 2, INF);
		time = 0;
		timestamp.assign(n * 2, 0);
	}
	void update(int l, int r, int x) {
		time++;
		for (; l && l + (l&-l) <= r; l += l & -l) {
			d[(n + l) / (l&-l)] = x;
			timestamp[(n + l) / (l&-l)] = time;
		}
		for (; l < r; r -= r & -r) {
			d[(n + r) / (r&-r) - 1] = x;
			timestamp[(n + r) / (r&-r) - 1] = time;
		}
	}
	int get(int i) {
		int ret = d[n + i];
		int max_time = timestamp[n + i];
		for (int j = (n + i) / 2; j > 0; j >>= 1) {
			if (max_time > timestamp[j])continue;
			max_time = timestamp[j];
			ret = d[j];
		}
		return ret;
	}
};

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<int> A(N); rep(i, 0, N) {
		cin >> A[i];
	}
	using T = pair<int, int>;
	vector<T> v1, v2;
	v1.emplace_back(0, 0);

	rep(i, 0, N) {
		for (auto t : v1) {
			int a, c;
			tie(a, c) = t;
			if (a < A[i]) {
				v2.emplace_back(A[i], c);
				v2.emplace_back(a + 1, c + 1);
			}
			else {
				v2.emplace_back(a + 1, c + 1);
			}
		}
		sort(all(v2));
		dump(v2);
		int m = v2.size();
		vector<T> w(m);
		rep(i, 0, m)w[i] = T(v2[i].second, i);
		sort(all(w));

		int minr = m;
		RangeUpdateQuery ruq(m);
		rep(i, 0, m) {
			if (w[i].second < minr) {
				ruq.update(w[i].second + 1, minr, 0);
				minr = w[i].second;
			}
		}
		
		vector<T> v3;
		rep(i, 0, m) {
			dump(i, ruq.get(i));
			if (ruq.get(i)) {
				v3.emplace_back(v2[i]);
			}
		}
		v2 = v3;
		v1.swap(v2);
		v2.clear();
	}
	dump(v1);
	int ans = N;
	for (auto t : v1) {
		chmin(ans, t.second);
	}
	cout << ans << endl;

	return 0;
}
0