結果

問題 No.631 Noelちゃんと電車旅行
ユーザー ミドリムシミドリムシ
提出日時 2018-01-05 23:20:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,953 bytes
コンパイル時間 973 ms
コンパイル使用メモリ 75,736 KB
実行使用メモリ 7,528 KB
最終ジャッジ日時 2023-08-24 21:17:25
合計ジャッジ時間 7,415 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
権限があれば一括ダウンロードができます

ソースコード

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