結果
問題 |
No.1441 MErGe
|
ユーザー |
![]() |
提出日時 | 2021-03-27 02:04:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,403 bytes |
コンパイル時間 | 4,067 ms |
コンパイル使用メモリ | 235,360 KB |
実行使用メモリ | 19,084 KB |
最終ジャッジ日時 | 2024-11-29 05:38:40 |
合計ジャッジ時間 | 15,861 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 2 |
other | WA * 4 RE * 24 |
ソースコード
#include "bits/stdc++.h" #include "atcoder/all" using namespace std; using namespace atcoder; //using mint = modint1000000007; //const int mod = 1000000007; //using mint = modint998244353; //const int mod = 998244353; //const int INF = 1e9; //const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n-1); i >= 0; --i) #define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define endl "\n" typedef pair<long long, int> P; //data struct S { long long num; int info; }; //lazy struct F { long long num; int info; }; //★自分で編集 //S*S->S P op(P s_l, P s_r) { return { s_l.first + s_r.first ,s_l.second + s_r.second }; } //op(a,e) = a = op(e,a)なeを返す P e() { return { (long long)0,0 }; } //f(x)を返す関数 P mapping(P f, P s) { if (f.second == -1) { return s; } return f; } //f(g(x))の合成関数 //c(ax+b)+d = acx+(bc+d) //rが先 P composition(P f, P g) { if (f.second == -1) { return g; } if (g.second == -1) { return f; } return f; } //mapping(id,a) = aなidを返す P id() { return P{ (long long)0,-1 }; } int target; bool f(P v) { return v.second <= target; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N >> Q; vector<pair<long long, int>> A(N); rep(i, N) { scanf("%lld", &A[i].first); A[i].second = 1; } lazy_segtree<pair<long long, int>, op, e, pair<long long, int>, mapping, composition, id> seg(A); rep(i, Q) { int T, l, r; scanf("%d %d %d", &T, &l, &r); target = r; r = seg.max_right<f>(0); target = l - 1; l = seg.max_right<f>(0); if (T == 1) { long long S = seg.prod(l, r).first; seg.apply(l, r, e()); seg.set(l, make_pair(S, 1)); } else { printf("%lld\n", seg.prod(l, r).first); } } /*vector<long long>A(N); vector<P>a(N); rep(i, N) { cin >> A[i]; a[i] = { A[i],1 }; } lazy_segtree<P, op, e, P, mapping, composition, id> seg(a); while (Q--) { int t, l, r; cin >> t >> l >> r; y = l - 1; int xl = seg.max_right<g>(0); y = r; int xr = seg.max_right<g>(0); if (1 == t) { //更新 int sum = seg.prod(xl, xr).first; seg.apply(xl, xr, { 0,0 }); seg.apply(xl, xl + 1, { sum ,1 }); } else { //取得 cout << seg.prod(xl, xr).first << endl; } }*/ return 0; }