結果
問題 | No.1705 Mode of long array |
ユーザー |
|
提出日時 | 2021-10-11 17:03:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 233 ms / 3,000 ms |
コード長 | 1,881 bytes |
コンパイル時間 | 2,253 ms |
コンパイル使用メモリ | 200,920 KB |
最終ジャッジ日時 | 2025-01-25 00:07:17 |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <math.h>#include <iomanip>#include <cstdint>#include <string>#include <sstream>template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }#define rep(i,n) for (int i = 0; i < (n); ++i)typedef long long ll;typedef long double ld;typedef unsigned long long ull;using P=pair<ll,ll>;const int INF=1001001001;const int mod=1e9+7;struct SegmentTree {private:int n;vector<P> node;public:SegmentTree(vector<P> v) {int sz = v.size();n = 1; while(n < sz) n *= 2;node.resize(2*n-1);for(int i=0; i<sz; i++) node[i+n-1] = v[i];for(int i=n-2; i>=0; i--) node[i] = max(node[2*i+1], node[2*i+2]);}void add(int x, ll val) {x += (n - 1);node[x].first += val;while(x > 0) {x = (x - 1) / 2;node[x] = max(node[2*x+1], node[2*x+2]);}}P getmax(int a, int b, int k=0, int l=0, int r=-1) {if(r < 0) r = n;if(r <= a || b <= l) return {0,0};if(a <= l && r <= b) return node[k];auto vl = getmax(a, b, 2*k+1, l, (l+r)/2);auto vr = getmax(a, b, 2*k+2, (l+r)/2, r);return max(vl, vr);}};void solve(){ll n,m;cin>>n>>m;vector<P>a(m);rep(i,m){cin>>a[i].first;a[i].second=i+1;}int q;cin>>q;SegmentTree seg(a);rep(i,q){ll t,x,y;cin>>t>>x>>y;x--;if(t==1){seg.add(x,y);}else if(t==2){seg.add(x,-y);}else{auto p=seg.getmax(0,m+1);cout<<p.second<<endl;}}}int main(){ios_base::sync_with_stdio(false);cin.tie(NULL);solve();return 0;}