結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー rii922
提出日時 2025-04-20 00:13:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 7,189 bytes
コンパイル時間 3,412 ms
コンパイル使用メモリ 294,600 KB
実行使用メモリ 19,716 KB
最終ジャッジ日時 2025-04-20 00:14:04
合計ジャッジ時間 7,573 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
#define rreps(i, n) for(int i=((int)(n)); i>0; --i)
#define all(v) (v).begin(), (v).end()
#define el '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
using vs = vector<string>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T> bool chmaxeq(T &a, const T &b) { if (a<=b) { a=b; return 1; } return 0; }
template<class T> bool chmineq(T &a, const T &b) { if (b<=a) { a=b; return 1; } return 0; }
bool yes(bool a=true) { cout << (a?"yes":"no") << el; return a; }
bool no(bool a=true) { cout << (a?"no":"yes") << el; return a; }
bool Yes(bool a=true) { cout << (a?"Yes":"No") << el; return a; }
bool No(bool a=true) { cout << (a?"No":"Yes") << el; return a; }
bool YES(bool a=true) { cout << (a?"YES":"NO") << el; return a; }
bool NO(bool a=true) { cout << (a?"NO":"YES") << el; return a; }
template<class T1, class T2> istream &operator>>(istream &is, pair<T1, T2> &p);
template<class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p);
template<class T> istream &operator>>(istream &is, vector<T> &v);
template<class T> ostream &operator<<(ostream &os, const vector<T> &v);
template<class T1, class T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
	return is >> p.first >> p.second;
}
template<class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	return os << p.first << ' ' << p.second;
}
template<class T>
istream &operator>>(istream &is, vector<T> &v) {
	int sz = v.size();
	for (int i = 0; i < sz; i++) is >> v[i];
	return is;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
	int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) os << ' ';
		os << v[i];
	}
	return os;
}
void _main();
int main() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(16); _main(); return 0; }


template<class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F)>
struct lazy_segtree {
	lazy_segtree(int n) {
		_init(n);
	}
	lazy_segtree(vector<S> &v) {
		_init(v.size());
		for (int i = 0; i < _sz; i++) _node[_n+i-1] = v[i];
		for (int i = _n-2; i >= 0; i--) _node[i] = op(_node[i*2+1], _node[i*2+2]);
	}
	lazy_segtree(int n, S x) {
		_init(n);
		for (int i = 0; i < _sz; i++) _node[_n+i-1] = x;
		for (int i = _n-2; i >= 0; i--) _node[i] = op(_node[i*2+1], _node[i*2+2]);
	}
	void set(int p, S x) {
		assert(0 <= p && p < _sz);
		p += _n - 1;
		int range = p;
		vector<int> pass;
		while (p > 0) {
			p = (p - 1) / 2;
			pass.push_back(p);
		}
		for (int i = pass.size()-1; i >= 0; i--) _eval(pass[i]);
		_node[range] = x;
		for (int i = 0; i < pass.size(); i++) {
			_node[pass[i]] = op(_node[pass[i]*2+1], _node[pass[i]*2+2]);
		}
	}
	S get(int p) {
		assert(0 <= p && p < _sz);
		p += _n - 1;
		int range = p;
		vector<int> pass;
		while (p > 0) {
			p = (p - 1) / 2;
			pass.push_back(p);
		}
		for (int i = pass.size()-1; i >= 0; i--) _eval(pass[i]);
		return _node[range];
	}
	S prod(int l, int r) {
		assert(0 <= l && l <= r && r <= _sz);
		return _prod(l, r, 0, 0, _n);
	}
	S all_prod() {
		return _node[0];
	}
	void apply(int l, int r, F f) {
		assert(0 <= l && l <= r && r <= _sz);
		_apply(l, r, f, 0, 0, _n);
	}
	int max_right(int l, bool (*f)(S)) {
		assert(0 <= l && l <= _sz);
		S pr = e();
		return _max_right(l, f, 0, 0, _n, pr);
	}
	int min_left(int r, bool (*f)(S)) {
		assert(0 <= r && r <= _sz);
		S pr = e();
		return _min_left(r, f, 0, 0, _n, pr);
	}
private:
	int _sz, _n;
	vector<S> _node;
	vector<optional<F>> _lazy;
	void _init(int n) {
		_sz = n;
		_n = 1;
		while (_n < _sz) _n *= 2;
		_node.resize(_n*2-1, e());
		_lazy.resize(_n*2-1, nullopt);
	}
	void _eval(int p) {
		if (_lazy[p]) {
			_node[p*2+1] = mapping(_lazy[p].value(), _node[p*2+1]);
			_node[p*2+2] = mapping(_lazy[p].value(), _node[p*2+2]);
			_lazy[p*2+1] = _lazy[p*2+1] ? composition(_lazy[p].value(), _lazy[p*2+1].value()) : _lazy[p].value();
			_lazy[p*2+2] = _lazy[p*2+2] ? composition(_lazy[p].value(), _lazy[p*2+2].value()) : _lazy[p].value();
			_lazy[p] = nullopt;
		}
	}
	S _prod(int l, int r, int p, int lp, int rp) {
		if (lp >= r || rp <= l) return e();
		if (lp >= l && rp <= r) return _node[p];
		_eval(p);
		int mp = (lp + rp) / 2;
		return op(_prod(l, r, p*2+1, lp, mp), _prod(l, r, p*2+2, mp, rp));
	}
	S _apply(int l, int r, F f, int p, int lp, int rp) {
		if (lp >= r || rp <= l) return _node[p];
		if (lp >= l && rp <= r) {
			_lazy[p] = _lazy[p] ? composition(f, _lazy[p].value()) : f;
			return _node[p] = mapping(f, _node[p]);
		}
		_eval(p);
		int mp = (lp + rp) / 2;
		return _node[p] = op(_apply(l, r, f, p*2+1, lp, mp), _apply(l, r, f, p*2+2, mp, rp));
	}
	int _max_right(int l, bool (*f)(S), int p, int lp, int rp, S &pr) {
		if (lp >= _sz) return _sz;
		if (rp <= l) return l;
		if (lp >= l && rp <= _sz) {
			S npr = op(pr, _node[p]);
			if (f(npr)) {
				pr = npr;
				return rp;
			}
			if (rp - lp == 1) return lp;
		}
		_eval(p);
		int mp = (lp + rp) / 2;
		int m = _max_right(l, f, p*2+1, lp, mp, pr);
		if (m < mp) return m;
		return _max_right(l, f, p*2+2, mp, rp, pr);
	}
	int _min_left(int r, bool (*f)(S), int p, int lp, int rp, S &pr) {
		if (lp >= r) return r;
		if (rp <= 0) return 0;
		if (rp <= r) {
			S npr = op(pr, _node[p]);
			if (f(npr)) {
				pr = npr;
				return lp;
			}
			if (rp - lp == 1) return rp;
		}
		_eval(p);
		int mp = (lp + rp) / 2;
		int m = _min_left(r, f, p*2+2, mp, rp, pr);
		if (m > mp) return m;
		return _min_left(r, f, p*2+1, lp, mp, pr);
	}
};

pl op(pl a, pl b) {
	return {a.first+b.first, a.second+b.second};
}
pl e() {
	return {0, 0};
}
pl mapping(ll f, pl x) {
	return {f*x.second, x.second};
}
ll composition(ll f, ll g) {
	return f;
}

void _main() {
	ll N, Q; cin >> N >> Q;
	lazy_segtree<pl, op, e, ll, mapping, composition> st(N, {1, 1});
	rep(_, Q) {
		ll q; cin >> q;
		if (q == 1) {
			ll x; cin >> x;
			x--;
			cout << st.prod(0, x).first << el;
		}
		else {
			ll x, c; cin >> x >> c;
			x--;
			if (st.prod(0, x).first <= c) continue;
			ll left1 = x;
			ll right1 = N;
			while (right1-left1 > 1) {
				ll mid = (left1+right1)/2;
				if (st.prod(0, mid).first <= mid-x+c) right1 = mid;
				else left1 = mid;
			}
			ll left2 = 0;
			ll right2 = x;
			while (right2-left2 > 1) {
				ll mid = (left2+right2)/2;
				if (st.prod(0, mid).first <= x-mid+c) left2 = mid;
				else right2 = mid;
			}
			st.apply(x, left1, 1);
			st.set(left1, {st.prod(0, right1).first-(left1-x+c), 1});
			st.apply(right2, x, -1);
			st.set(left2, {x-right2+c-st.prod(0, left2).first, 1});
		}
	}
}
0