結果

問題 No.865 24時間降水量
コンテスト
ユーザー ahe100
提出日時 2019-08-16 23:16:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 548 ms / 2,000 ms
コード長 1,903 bytes
コンパイル時間 1,728 ms
コンパイル使用メモリ 172,980 KB
実行使用メモリ 10,524 KB
最終ジャッジ日時 2024-09-22 22:08:50
合計ジャッジ時間 4,580 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)

/*
*/

struct SegTree{
    vector<int> data_;
    static int operation(int op1, int op2){
        return max(op1,op2);
    }
    SegTree(const vector<int>& src){
        data_.resize(src.size() * 2);
        for(size_t i = 0; i < src.size(); i++) update(i, src[i]);//ここ大きい順に作ればO(n)でいける
    }
    int query(size_t begin, size_t end, int init) const{
        begin += data_.size()/2; end += data_.size()/2;
        for(; begin < end; begin /= 2, end /= 2){
            if(begin & 1) init = operation(init, data_[begin++]);
            if(end & 1) init = operation(init, data_[end-1]);
        }
        return init;
    }
    void update(size_t pos, int val){
        pos += data_.size()/2;
        data_[pos] = val;
        while((pos /= 2) > 0){
            data_[pos] = operation(data_[pos*2], data_[pos*2+1]);
        }
    }
};

//===================================

ll n,a[200010],q,t[200010],v[200010];
vector<int> sum;

void init(){
	cin>>n;
	rep(i,n)cin>>a[i];
	cin>>q;
	rep(i,q){
		cin>>t[i]>>v[i];
		t[i]--;
	}
	rep(i,n-23){
		int tmp=0;
		rep(j,24)tmp+=a[i+j];
		sum.push_back(tmp);
	}
}

int main(void){
	init();
	SegTree sg(sum);
	// cerr<<"before: ";
	// rep(i,sum.size())cerr<<sum[i]<<" ";
	// cerr<<endl;
	rep(i,q){
		int d = v[i]-a[t[i]];
		irep(j,24){
			if(t[i]-j<0)continue;
			if(t[i]-j>sum.size()-1)break;
			int tmp = sg.query(t[i]-j,t[i]+1-j,0);
			// cerr<<j<<": "<<tmp<<", "<<d<<endl;
			sg.update(t[i]-j,tmp+d);
		}
		a[t[i]]=v[i];
		cout<<sg.query(0,sum.size(),0)<<endl;
	}
	// cerr<<"after: ";
	// rep(i,sum.size())cerr<<sum[i]<<" ";
	// cerr<<endl;
	return 0;
}
0