結果

問題 No.1705 Mode of long array
ユーザー asaringo
提出日時 2021-10-09 00:21:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 388 ms / 3,000 ms
コード長 1,948 bytes
コンパイル時間 2,089 ms
コンパイル使用メモリ 186,124 KB
実行使用メモリ 9,928 KB
最終ジャッジ日時 2024-07-23 09:00:29
合計ジャッジ時間 12,146 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef pair<int,int> P ;
#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define rrep(i,a,b) for(int i = a ; i < b ; i++)
const int MAX_N = 1 << 18 ;
template<typename T>
struct SegmentTree{
int n ;
T dat[2 * MAX_N - 1] ;
SegmentTree(int n_){
n = 1 ;
while(n < n_) n *= 2 ;
memset(dat,0,sizeof(dat)) ;
}
void add(int k , T x){
k += n - 1 ;
dat[k] += x ;
while(k > 0){
k = (k - 1) / 2 ;
dat[k] = max(dat[2*k+1],dat[2*k+2]) ;
}
}
T sub_query(int a , int b , int k , int l , int r){
if(r <= a || b <= l) return -1e18 ;
if(a <= l && r <= b) return dat[k] ;
T lef = sub_query(a,b,2*k+1,l,(l+r)/2) ;
T rig = sub_query(a,b,2*k+2,(l+r)/2,r) ;
return max(lef,rig) ;
}
T query(int a , int b){
return sub_query(a,b,0,0,n) ;
}
T solve(){
int lef = 0 , rig = n ;
while(rig - lef > 1){
ll mid = (lef + rig) / 2 ;
if(query(lef,mid) <= query(mid,rig)) lef = mid ;
else rig = mid ;
}
return lef ;
}
};
ll n , m , q ;
ll A[101010] , B[101010] , C[101010] ;
unordered_map<int,int> mp ;
int main(){
cin >> n >> m ;
SegmentTree<ll> SegTree(202020) ;
rep(i,m) cin >> A[i] ;
rep(i,m) SegTree.add(i,A[i]) ;
cin >> q ;
int id = m ;
rep(i,q){
ll t , x , y ;
cin >> t >> x >> y ;
x-- ;
if(x >= m){
mp[id] = x ;
mp[x] = id ;
x = id ;
id++ ;
}
if(t == 1){
SegTree.add(x,y) ;
}
if(t == 2){
SegTree.add(x,-y) ;
}
if(t == 3){
ll res = SegTree.solve() ;
if(res >= m) res = mp[res] ;
else res++ ;
cout << res << endl ;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0