結果
問題 | No.1705 Mode of long array |
ユーザー |
![]() |
提出日時 | 2021-10-08 22:25:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 302 ms / 3,000 ms |
コード長 | 1,479 bytes |
コンパイル時間 | 2,321 ms |
コンパイル使用メモリ | 200,172 KB |
最終ジャッジ日時 | 2025-01-24 22:33:02 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include <bits/stdc++.h> using namespace std; int inf = 1001001001; template <typename T> struct SegmentTree { int n; vector<T> dat; SegmentTree() {} SegmentTree(int N) { n = 1; while(n < N) { n *= 2; } dat.resize(2*n-1,{-inf,-inf}); } void update(int x, long long val,int val2) { x += (n-1); dat[x].first = val; dat[x].second = val2; while(x > 0) { x = (x-1)/2; dat[x] = max(dat[2*x+1],dat[2*x+2]); } } T query(int a, int b, int k, int l, int r) { if(r <= a || b <= l) return {-inf,-inf}; if(a <= l && r <= b) return dat[k]; T vl = query(a, b, 2*k+1, l, (l+r)/2); T vr = query(a, b, 2*k+2, (l+r)/2, r); return max(vl, vr); } T query(int a,int b) {//[a,b) return query(a,b,0,0,n); } }; int main() { long long N,M; cin >> N >> M; vector<long long>a(M); SegmentTree<pair<long long,int>>Seg(M); for(int i = 0; i < M; i++) { cin >> a[i]; Seg.update(i,a[i],i); } int Q; cin >> Q; while (Q--) { long long t,x,y; cin >> t >> x >> y; x--; if(t == 1) { a[x] += y; Seg.update(x,a[x],x); } if(t == 2) { a[x] -= y; Seg.update(x,a[x],x); } if(t == 3) { cout << Seg.query(0,M).second+1 << endl; } } }