結果

問題 No.1441 MErGe
ユーザー first_vilfirst_vil
提出日時 2020-11-26 17:11:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 335 ms / 1,000 ms
コード長 2,695 bytes
コンパイル時間 2,389 ms
コンパイル使用メモリ 215,968 KB
実行使用メモリ 20,360 KB
最終ジャッジ日時 2024-10-12 06:02:13
合計ジャッジ時間 12,356 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 4 ms
6,820 KB
testcase_04 AC 4 ms
6,820 KB
testcase_05 AC 7 ms
6,816 KB
testcase_06 AC 7 ms
6,820 KB
testcase_07 AC 7 ms
6,820 KB
testcase_08 AC 53 ms
7,384 KB
testcase_09 AC 53 ms
7,168 KB
testcase_10 AC 81 ms
7,040 KB
testcase_11 AC 71 ms
6,816 KB
testcase_12 AC 83 ms
7,252 KB
testcase_13 AC 285 ms
19,768 KB
testcase_14 AC 292 ms
19,764 KB
testcase_15 AC 288 ms
19,316 KB
testcase_16 AC 286 ms
19,552 KB
testcase_17 AC 281 ms
19,392 KB
testcase_18 AC 169 ms
17,220 KB
testcase_19 AC 193 ms
18,572 KB
testcase_20 AC 149 ms
16,772 KB
testcase_21 AC 133 ms
12,516 KB
testcase_22 AC 168 ms
12,196 KB
testcase_23 AC 335 ms
20,352 KB
testcase_24 AC 329 ms
20,356 KB
testcase_25 AC 321 ms
20,356 KB
testcase_26 AC 335 ms
20,352 KB
testcase_27 AC 335 ms
20,356 KB
testcase_28 AC 197 ms
20,356 KB
testcase_29 AC 198 ms
20,360 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define tp(a,i) get<i>(a)
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T>inline void print(const T& a) { cout << a << "\n"; }
template<class T>inline void print(const vector<T>& v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); }
template<class T>inline T sum(const vector<T>& a, int l, int r) { return a[r] - (l == 0 ? 0 : a[l - 1]); }

template<class Op> class SegmentTree {
	using T = typename Op::T;
	int len, n;
	vector<T> dat;
	vector<pair<int, int>> range;
public:
	SegmentTree(const vector<T>& v) : n(v.size()) {
		for (len = 1; len < n; len <<= 1);
		dat.resize(len << 1, Op::unit);
		range.resize(len << 1);
		for (int i = 0; i < n; ++i)dat[i + len] = v[i];
		for (int i = 0; i < len; ++i)
			range[i + len] = make_pair(i, i + 1);
		for (int i = len - 1; 0 < i; --i) {
			dat[i] = Op::merge(dat[i << 1], dat[i << 1 | 1]);
			range[i] = make_pair(range[i << 1].first, range[i << 1 | 1].second);
		}
	}
	inline void update(int idx, const T a) {
		idx += len;
		dat[idx] = Op::update(dat[idx], a);
		for (idx >>= 1; 0 < idx; idx >>= 1)
			dat[idx] = Op::merge(dat[idx << 1], dat[idx << 1 | 1]);
	}
	inline int binary_search(const T a) {
		if (!Op::check(dat[1], a))return n;
		T cur = Op::unit;
		int idx = 2;
		for (; idx < len << 1; idx <<= 1) {
			if (!Op::check(Op::merge(cur, dat[idx]), a))
				cur = Op::merge(cur, dat[idx++]);
		}
		return min((idx >> 1) - len, n);
	}
};
template<class Type> struct node {
	using T = Type;
	inline static T unit = 0;
	inline static T merge(T vl, T vr) { return vl + vr; }
	inline static T update(T vl, T vr) { return vl + vr; }
	inline static T check(T vl, T vr) { return vl >= vr; }
};

int main() {
    init();

    int n, q; cin >> n >> q;
    VL a(n); cin >> a;
    SegmentTree<node<int>> seg(VI(n, 1));
    set<int> s;
    FOR(i, 0, n) {
        if (0 < i)a[i] += a[i - 1];
        s.emplace(i);
    }
    while (q--) {
        int t, l, r; cin >> t >> l >> r;
        if (t == 1) {
            int d = r - l;
            l = seg.binary_search(l);
            r = seg.binary_search(r);
            auto it = s.find(l);
            FOR(i, 0, d)seg.update(*++it, -1);
            FOR(i, 0, d)s.erase(s.upper_bound(l));
        }
        else cout << sum(a, seg.binary_search(l), seg.binary_search(r + 1) - 1) << "\n";
    }

    return 0;
}
0