結果
問題 | No.1705 Mode of long array |
ユーザー |
![]() |
提出日時 | 2023-10-19 12:21:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 72 ms / 3,000 ms |
コード長 | 2,399 bytes |
コンパイル時間 | 1,338 ms |
コンパイル使用メモリ | 125,556 KB |
最終ジャッジ日時 | 2025-02-17 08:21:36 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<cstring>#include<cassert>#include<cmath>#include<ctime>#include<iomanip>#include<numeric>#include<stack>#include<queue>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<bitset>#include<random>using namespace std;template<class T,T (*op)(T,T),T (*e)()> struct SegmentTree{private:int siz;vector<T> node;public:SegmentTree(int n) noexcept{siz = 1;while(siz < n) siz <<= 1;node.assign(2*siz-1,e());}void replace(int pos,T x) noexcept {func_update(pos,x,[](T u,T v){return u = v;});}void add(int pos,T x) noexcept {func_update(pos,x,[](T u,T v){return u+v;});}void func_update(int pos,T x) noexcept {func_update(pos,x,op);}void func_update(int pos,T x,T (*func)(T,T)) noexcept{assert(0 <= pos && pos < siz);pos += siz - 1;node[pos] = func(node[pos],x);while(pos){pos = (pos-1)/2;node[pos] = op(node[2*pos+1],node[2*pos+2]);}}T operator [](int pos) noexcept{assert(0 <= pos && pos < siz);return node[pos+siz-1];}T prod(int l,int r) noexcept{assert(0 <= l && l <= r && r <= siz);l += siz-1;r += siz-1;T Lval = e();T Rval = e();while(l < r){if(!(l & 1)) Lval = op(Lval,node[l++]);if(!(r & 1)) Rval = op(node[--r],Rval);l >>= 1;r >>= 1;}return op(Lval,Rval);}T prod() noexcept {return node[0];}};long long N;int M;using P = pair<long long,int>;P op(P a,P b) {return max(a,b);}P e() {return make_pair(0,-1);}void solve(){cin >> N >> M;SegmentTree<P,op,e> seg(M);for(int i = 0;i < M;i++){long long A;cin >> A;seg.replace(i,make_pair(A,i));}int Q;cin >> Q;for(;Q--;){int t,x;long long y;cin >> t >> x >> y;if(t == 1){x--;P cur = seg[x];cur.first += y;seg.replace(x,cur);}else if(t == 2){x--;P cur = seg[x];cur.first -= y;assert(cur.first >= 0);seg.replace(x,cur);}else cout << seg.prod().second+1 << "\n";}}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1;//cin >> tt;while(tt--) solve();}