結果
問題 |
No.1441 MErGe
|
ユーザー |
![]() |
提出日時 | 2021-03-27 01:54:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,882 bytes |
コンパイル時間 | 3,980 ms |
コンパイル使用メモリ | 235,396 KB |
実行使用メモリ | 20,296 KB |
最終ジャッジ日時 | 2024-11-29 05:23:31 |
合計ジャッジ時間 | 12,547 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 2 WA * 26 |
ソースコード
#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 P{ 0,0 }; } //f(x)を返す関数 P mapping(P f, P s) { if (f.second == -1) { return s; } return { f.first,f.second }; } //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{ 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<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; target = l - 1; int xl = seg.max_right<f>(0); target = r; int xr = seg.max_right<f>(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; }