結果

問題 No.711 競技レーティング単調増加
ユーザー minamiminami
提出日時 2018-06-29 23:20:06
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,756 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 TLE -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
権限があれば一括ダウンロードができます

ソースコード

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