結果

問題 No.631 Noelちゃんと電車旅行
コンテスト
ユーザー ミドリムシ
提出日時 2018-01-05 23:20:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,953 bytes
コンパイル時間 650 ms
コンパイル使用メモリ 76,076 KB
実行使用メモリ 7,372 KB
最終ジャッジ日時 2024-12-23 07:19:11
合計ジャッジ時間 9,033 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define this_item segment_tree[item_number]

struct item{
    long maximum, laziness;
};

int N, M;
vector<long> train_time;
int segment_tree_size;
vector<item> segment_tree;

void InitSize(){
    segment_tree_size = 1;
    while(segment_tree_size < N){
        segment_tree_size *= 2;
    }
}

void InitNode(){
    for(int i = 0; i < N; i++){
        segment_tree[segment_tree_size - 1 + i].maximum = train_time[i];
    }
    if(segment_tree_size == 1){
        return;
    }
    for(int i = segment_tree_size - 2; i >= 0; i--){
        segment_tree[i].maximum = max(segment_tree[i * 2 + 1].maximum, segment_tree[i * 2 + 2].maximum);
    }
}

inline void update_laziness(int length, int item_number){
    segment_tree[item_number * 2 + 1].laziness = max(segment_tree[item_number * 2 + 1].laziness, this_item.laziness);
    segment_tree[item_number * 2 + 2].laziness = max(segment_tree[item_number * 2 + 2].laziness, this_item.laziness);
    this_item.maximum = max(this_item.maximum, this_item.laziness);
    this_item.laziness = 0;
}

long Add(int looking_left, int looking_right, int item_number, int left, int right, long value){
    if(looking_right <= left || right <= looking_left){
        return max(this_item.maximum, this_item.laziness);
    }else if(left <= looking_left && looking_right <= right){
        this_item.laziness = max(this_item.laziness, value);
        return max(this_item.maximum, this_item.laziness);
    }else{
        update_laziness(looking_right - looking_left, item_number);
        int middle = (looking_left + looking_right) / 2;
        return this_item.maximum = max(Add(looking_left, middle, item_number * 2 + 1, left, right, value), Add(middle, looking_right, item_number * 2 + 2, left, right, value));
    }
}

long range_maximum(int looking_left, int looking_right, int item_number, int left, int right){
    if(looking_right <= left || right <= looking_left){
        return 0;
    }else if(left <= looking_left && looking_right <= right){
        return max(this_item.maximum, this_item.laziness);
    }else{
        update_laziness(looking_right - looking_left, item_number);
        int middle = (looking_left + looking_right) / 2;
        return max(range_maximum(looking_left, middle, item_number * 2 + 1, left, right), range_maximum(middle, looking_right, item_number * 2 + 2, left, right));
    }
}

int main(){
    cin >> N;
    N--;
    for(int i = 0; i < N; i++){
        long this_time;
        cin >> this_time;
        train_time.push_back(this_time + (N - i) * 3);
    }
    cin >> M;
    segment_tree.resize(N * 2 - 1);
    InitSize();
    InitNode();
    for(int i = 0; i < M; i++){
        int L, R;
        long D;
        cin >> L >> R >> D;
        cout << L << R << D << endl;
        Add(0, segment_tree_size, 0, L - 1, R, D);
        cout << range_maximum(0, segment_tree_size, 0, 0, N) << endl;
    }
}
0