#708520 (C++17) No.1705 Mode of long array

提出ソース

結果

問題	No.1705 Mode of long array
ユーザー	Example0911
提出日時	2021-10-21 18:53:37
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	186 ms / 3,000 ms
コード長	3,527 bytes
コンパイル時間	2,329 ms
コンパイル使用メモリ	208,908 KB
実行使用メモリ	6,340 KB
最終ジャッジ日時	2023-10-21 13:46:36
合計ジャッジ時間	13,684 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,348 KB
testcase_01	AC	1 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	3 ms 4,348 KB
testcase_04	AC	3 ms 4,348 KB
testcase_05	AC	3 ms 4,348 KB
testcase_06	AC	6 ms 4,348 KB
testcase_07	AC	8 ms 4,348 KB
testcase_08	AC	8 ms 4,348 KB
testcase_09	AC	7 ms 4,348 KB
testcase_10	AC	7 ms 4,348 KB
testcase_11	AC	7 ms 4,348 KB
testcase_12	AC	7 ms 4,348 KB
testcase_13	AC	78 ms 5,548 KB
testcase_14	AC	72 ms 4,756 KB
testcase_15	AC	78 ms 4,348 KB
testcase_16	AC	92 ms 4,348 KB
testcase_17	AC	66 ms 4,348 KB
testcase_18	AC	67 ms 4,348 KB
testcase_19	AC	98 ms 4,348 KB
testcase_20	AC	61 ms 4,348 KB
testcase_21	AC	72 ms 5,284 KB
testcase_22	AC	107 ms 6,076 KB
testcase_23	AC	41 ms 4,348 KB
testcase_24	AC	41 ms 4,348 KB
testcase_25	AC	41 ms 4,348 KB
testcase_26	AC	42 ms 4,348 KB
testcase_27	AC	42 ms 4,348 KB
testcase_28	AC	41 ms 4,348 KB
testcase_29	AC	41 ms 4,348 KB
testcase_30	AC	41 ms 4,348 KB
testcase_31	AC	41 ms 4,348 KB
testcase_32	AC	42 ms 4,348 KB
testcase_33	AC	97 ms 6,340 KB
testcase_34	AC	92 ms 6,340 KB
testcase_35	AC	89 ms 6,340 KB
testcase_36	AC	87 ms 6,340 KB
testcase_37	AC	92 ms 6,340 KB
testcase_38	AC	90 ms 6,340 KB
testcase_39	AC	89 ms 6,340 KB
testcase_40	AC	90 ms 6,340 KB
testcase_41	AC	86 ms 6,340 KB
testcase_42	AC	85 ms 6,340 KB
testcase_43	AC	175 ms 6,340 KB
testcase_44	AC	186 ms 6,340 KB
testcase_45	AC	156 ms 6,340 KB
testcase_46	AC	165 ms 6,340 KB
testcase_47	AC	158 ms 6,340 KB
testcase_48	AC	155 ms 6,340 KB
testcase_49	AC	88 ms 6,340 KB
testcase_50	AC	91 ms 6,340 KB
testcase_51	AC	88 ms 6,340 KB
testcase_52	AC	93 ms 6,340 KB
testcase_53	AC	90 ms 6,340 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include "bits/stdc++.h"

#define int long long

using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = (1LL << 61);
ll mod = 1000000007;

/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
	set(int i, T x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
	update(i,x): i 番目の要素を x に更新。O(log(n))
	query(a,b): [a,b) での最小の要素を取得。O(log(n))
	find_rightest(a,b,x): [a,b) で x以下の要素を持つ最右位置を求める。O(log(n))
	find_leftest(a,b,x): [a,b) で x以下の要素を持つ最左位置を求める。O(log(n))
*/
template <typename T>
struct RMQ {
	const T e = numeric_limits<T>::max();
	function<T(T, T)> fx = [](T x1, T x2) -> T { return min(x1, x2); };
	int n;
	vector<T> dat;
	RMQ(int n_) : n(), dat(n_ * 4, e) {
		int x = 1;
		while (n_ > x) {
			x *= 2;
		}
		n = x;
	}
	void set(int i, T x) { dat[i + n - 1] = x; }
	void build() {
		for (int k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
	}
	void update(int i, T x) {
		i += n - 1;
		dat[i] = x;
		while (i > 0) {
			i = (i - 1) / 2;  // parent
			dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
		}
	}
	// the minimum element of [a,b)
	T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
	T query_sub(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) {
			return e;
		}
		else if (a <= l && r <= b) {
			return dat[k];
		}
		else {
			T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
			T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
			return fx(vl, vr);
		}
	}
	int find_rightest(int a, int b, T x) { return find_rightest_sub(a, b, x, 0, 0, n); }
	int find_leftest(int a, int b, T x) { return find_leftest_sub(a, b, x, 0, 0, n); }
	int find_rightest_sub(int a, int b, T x, int k, int l, int r) {
		if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
			return a - 1;
		}
		else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
			return (k - (n - 1));
		}
		else {
			int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
			if (vr != a - 1) {  // 右の部分木を見て a-1 以外ならreturn
				return vr;
			}
			else {  // 左の部分木を見て値をreturn
				return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
			}
		}
	}
	int find_leftest_sub(int a, int b, T x, int k, int l, int r) {
		if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
			return b;
		}
		else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
			return (k - (n - 1));
		}
		else {
			int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
			if (vl != b) {  // 左の部分木を見て b 以外ならreturn
				return vl;
			}
			else {  // 右の部分木を見て値をreturn
				return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
			}
		}
	}
};
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, M; cin >> N >> M;
	RMQ<int>rmq(M);
	for (int i = 0; i < M; i++) {
		int a; cin >> a;
		rmq.update(i, -a);
	}
	int Q; cin >> Q;
	for (int i = 0; i < Q; i++) {
		int T, X, Y; cin >> T >> X >> Y; X--;
		if (T == 1) {
			int now = rmq.query(X, X + 1);
			rmq.update(X, now - Y);
		}
		else if (T == 2) {
			int now = rmq.query(X, X + 1);
			rmq.update(X, now + Y);
		}
		else {
			int now = rmq.query(0, M);
			cout << rmq.find_rightest(0, M, now) + 1 << endl;
		}
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード