#807559 (C++17) No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに

提出ソース

結果

問題	No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに
ユーザー	bayashiko
提出日時	2022-10-15 00:53:26
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	1,838 ms / 6,000 ms
コード長	11,108 bytes
コンパイル時間	4,419 ms
コンパイル使用メモリ	236,204 KB
実行使用メモリ	113,908 KB
最終ジャッジ日時	2023-09-09 01:32:16
合計ジャッジ時間	56,952 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	654 ms 105,036 KB
testcase_04	AC	1,294 ms 110,744 KB
testcase_05	AC	588 ms 55,996 KB
testcase_06	AC	1,155 ms 108,408 KB
testcase_07	AC	1,288 ms 108,840 KB
testcase_08	AC	1,299 ms 110,044 KB
testcase_09	AC	494 ms 55,260 KB
testcase_10	AC	494 ms 55,620 KB
testcase_11	AC	854 ms 58,284 KB
testcase_12	AC	876 ms 58,800 KB
testcase_13	AC	564 ms 56,428 KB
testcase_14	AC	502 ms 17,372 KB
testcase_15	AC	1,404 ms 111,636 KB
testcase_16	AC	1,046 ms 107,536 KB
testcase_17	AC	420 ms 19,852 KB
testcase_18	AC	1,800 ms 112,596 KB
testcase_19	AC	1,789 ms 113,000 KB
testcase_20	AC	1,736 ms 113,224 KB
testcase_21	AC	1,783 ms 112,448 KB
testcase_22	AC	1,822 ms 113,616 KB
testcase_23	AC	1,814 ms 112,568 KB
testcase_24	AC	1,810 ms 113,692 KB
testcase_25	AC	1,787 ms 113,724 KB
testcase_26	AC	1,814 ms 113,548 KB
testcase_27	AC	1,805 ms 113,092 KB
testcase_28	AC	1,838 ms 113,908 KB
testcase_29	AC	1,610 ms 113,524 KB
testcase_30	AC	1,458 ms 112,760 KB
testcase_31	AC	1,425 ms 113,672 KB
testcase_32	AC	1,494 ms 112,332 KB
testcase_33	AC	927 ms 113,604 KB
testcase_34	AC	1,000 ms 112,512 KB
testcase_35	AC	1,013 ms 112,648 KB
testcase_36	AC	1,006 ms 112,888 KB
testcase_37	AC	988 ms 112,828 KB
testcase_38	AC	73 ms 13,512 KB
testcase_39	AC	427 ms 23,808 KB
testcase_40	AC	381 ms 112,532 KB
testcase_41	AC	1 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#if defined(LOCAL)
#include<stdc++.h>
#else
#include<bits/stdc++.h>
#endif
#include<random>
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
using namespace std;
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
//namespace mp=boost::multiprecision;
//#define mulint mp::cpp_int
//#define mulfloat mp::cpp_dec_float_100
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
//#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define MINF (lint)(2e18)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define flc(x) __builtin_popcountll(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
//#define vec vector<lint>
#define nep(x) next_permutation(all(x))
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=3e5+5;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//vector<int> bucket[MAX_N/1000];
//constexpr int MOD=1000000007;
constexpr int MOD=998244353;
/*#include<atcoder/all>
using namespace atcoder;
typedef __int128_t llint;*/

// Segment Tree Beats
// - l<=i<r について、 A_i の値を min(A_i, x) に更新
// - l<=i<r について、 A_i の値を max(A_i, x) に更新
// - l<=i<r の中の A_i の最大値を求める
// - l<=i<r の中の A_i の最小値を求める
// - l<=i<r の A_i の和を求める
// - l<=i<r について、 A_i の値に x を加える
// - l<=i<r について、 A_i の値を x に更新

class SegmentTreeBeats{
    static const lint inf = 1e18;
    struct Node{
        Node *left, *right;
        lint max_v, smax_v, max_c;
        lint min_v, smin_v, min_c;
        lint sum;
        lint len, ladd, lval;

        Node() : left(0), right(0), ladd(0), lval(inf) {}

        void init(lint x){
            max_v = min_v = sum = x;
            smax_v = -inf;
            smin_v = inf;
            max_c = min_c = 1;
        }

        void init_empty(){
            max_v = smax_v = -inf;
            min_v = smin_v = inf;
            max_c = min_c = 0;
        }

        void update_max(lint x){
            sum += (x - max_v) * max_c;

            if (max_v == min_v){
                max_v = min_v = x;
            }
            else if (max_v == smin_v){
                max_v = smin_v = x;
            }
            else{
                max_v = x;
            }

            if (lval != inf && x < lval){
                lval = x;
            }
        }

        void update_min(lint x){
            sum += (x - min_v) * min_c;

            if (max_v == min_v){
                max_v = min_v = x;
            }
            else if (max_v == smin_v){
                min_v = smax_v = x;
            }
            else{
                min_v = x;
            }

            if (lval != inf && lval < x){
                lval = x;
            }
        }

        void addalint(lint x)
        {
            max_v += x;
            if (smax_v != -inf) smax_v += x;
            min_v += x;
            if (smin_v != inf) smin_v += x;
            sum += len * x;
            if (lval != inf){
                lval += x;
            }
            else{
                ladd += x;
            }
        }

        void updatealint(lint x){
            max_v = min_v = x;
            smax_v = -inf;
            smin_v = inf;
            max_c = min_c = len;

            sum = len * x;
            lval = x;
            ladd = 0;
        }

        void push(){

            if (lval != inf){
                left->updatealint(lval);
                right->updatealint(lval);
                lval = inf;
                return;
            }

            if (ladd != 0){
                left->addalint(ladd);
                right->addalint(ladd);
                ladd = 0;
            }

            if (max_v < left->max_v){
                left->update_max(max_v);
            }
            if (left->min_v < min_v){
                left->update_min(min_v);
            }

            if (max_v < right->max_v){
                right->update_max(max_v);
            }
            if (right->min_v < min_v){
                right->update_min(min_v);
            }
        }

        void update(){
            sum = left->sum + right->sum;

            if (left->max_v < right->max_v){
                max_v = right->max_v;
                max_c = right->max_c;
                smax_v = max(left->max_v, right->smax_v);
            }
            else if (left->max_v > right->max_v){
                max_v = left->max_v;
                max_c = left->max_c;
                smax_v = max(left->smax_v, right->max_v);
            }
            else{
                max_v = left->max_v;
                max_c = left->max_c + right->max_c;
                smax_v = max(left->smax_v, right->smax_v);
            }

            if (left->min_v < right->min_v){
                min_v = left->min_v;
                min_c = left->min_c;
                smin_v = min(left->smin_v, right->min_v);
            }
            else if (left->min_v > right->min_v){
                min_v = right->min_v;
                min_c = right->min_c;
                smin_v = min(left->min_v, right->smin_v);
            }
            else{
                min_v = left->min_v;
                min_c = left->min_c + right->min_c;
                smin_v = min(left->smin_v, right->smin_v);
            }
        }
    };

    int n, n0;
    Node *root;

    void _update_min(lint x, int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a || nd->max_v <= x){
            return;
        }
        if (a <= l && r <= b && nd->smax_v < x){
            nd->update_max(x);
            return;
        }

        nd->push();
        _update_min(x, a, b, nd->left, l, (l + r) / 2);
        _update_min(x, a, b, nd->right, (l + r) / 2, r);
        nd->update();
    }

    void _update_max(lint x, int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a || x <= nd->min_v){
            return;
        }
        if (a <= l && r <= b && x < nd->smin_v){
            nd->update_min(x);
            return;
        }

        nd->push();
        _update_max(x, a, b, nd->left, l, (l + r) / 2);
        _update_max(x, a, b, nd->right, (l + r) / 2, r);
        nd->update();
    }

    void _add_val(lint x, int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a){
            return;
        }
        if (a <= l && r <= b){
            nd->addalint(x);
            return;
        }

        nd->push();
        _add_val(x, a, b, nd->left, l, (l + r) / 2);
        _add_val(x, a, b, nd->right, (l + r) / 2, r);
        nd->update();
    }

    void _update_val(lint x, int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a){
            return;
        }
        if (a <= l && r <= b){
            nd->updatealint(x);
            return;
        }

        nd->push();
        _update_val(x, a, b, nd->left, l, (l + r) / 2);
        _update_val(x, a, b, nd->right, (l + r) / 2, r);
        nd->update();
    }

    lint _query_max(int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a){
            return -inf;
        }
        if (a <= l && r <= b){
            return nd->max_v;
        }
        nd->push();
        lint lv = _query_max(a, b, nd->left, l, (l + r) / 2);
        lint rv = _query_max(a, b, nd->right, (l + r) / 2, r);
        return max(lv, rv);
    }

    lint _query_min(int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a){
            return inf;
        }
        if (a <= l && r <= b){
            return nd->min_v;
        }
        nd->push();
        lint lv = _query_min(a, b, nd->left, l, (l + r) / 2);
        lint rv = _query_min(a, b, nd->right, (l + r) / 2, r);
        return min(lv, rv);
    }

    lint _query_sum(int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a){
            return 0;
        }
        if (a <= l && r <= b){
            return nd->sum;
        }
        nd->push();
        lint lv = _query_sum(a, b, nd->left, l, (l + r) / 2);
        lint rv = _query_sum(a, b, nd->right, (l + r) / 2, r);
        return lv + rv;
    }

public:
    SegmentTreeBeats(int n, vector<lint> a) : n(n){
        n0 = 1;
        while (n0 < n) n0 <<= 1;

        Node *nds = new Node[2 * n0];
        root = nds;

        nds[0].len = n0;
        for (int i = 0; i < n0 - 1; ++i){
            nds[i].left = &nds[2 * i + 1];
            nds[i].right = &nds[2 * i + 2];
            nds[2 * i + 1].len = nds[2 * i + 2].len = (nds[i].len >> 1);
        }

        for (int i = 0; i < n; ++i) nds[n0 - 1 + i].init(a[i]);
        for (int i = n; i < n0; ++i) nds[n0 - 1 + i].init_empty();
        for (int i = n0 - 2; i >= 0; i--) nds[i].update();
    }
    SegmentTreeBeats(int n) : n(n){
        n0 = 1;
        while (n0 < n) n0 <<= 1;

        Node *nds = new Node[2 * n0];
        root = nds;

        nds[0].len = n0;
        for (int i = 0; i < n0 - 1; ++i){
            nds[i].left = &nds[2 * i + 1];
            nds[i].right = &nds[2 * i + 2];
            nds[2 * i + 1].len = nds[2 * i + 2].len = (nds[i].len >> 1);
        }

        for (int i = 0; i < n; ++i) nds[n0 - 1 + i].init(0);
        for (int i = n; i < n0; ++i) nds[n0 - 1 + i].init_empty();
        for (int i = n0 - 2; i >= 0; i--) nds[i].update();
    }

    void update_min(int a, int b, lint x){
        _update_min(x, a, b, root, 0, n0);
    }

    void update_max(int a, int b, lint x){
        _update_max(x, a, b, root, 0, n0);
    }

    void add_val(int a, int b, lint x){
        _add_val(x, a, b, root, 0, n0);
    }

    void update_val(int a, int b, lint x){
        _update_val(x, a, b, root, 0, n0);
    }

    lint query_max(int a, int b){
        return _query_max(a, b, root, 0, n0);
    }

    lint query_min(int a, int b){
        return _query_min(a, b, root, 0, n0);
    }

    lint query_sum(int a, int b){
        return _query_sum(a, b, root, 0, n0);
    }
};


int main(void){
    lint N;
    cin >> N;
    lint A[N],T[N];
    rep(i,N) cin >> A[i] >> T[i];
    vector<pair<plint,plint>> qs;
    int Q;
    cin >> Q;
    lint ans[Q]={};
    rep(i,Q){
        lint D,L,R;
        cin >> D >> L >> R;
        L--;
        qs.push_back({{D,i},{L,R}});
    }
    sort(all(qs));
    SegmentTreeBeats plus(N),minus(N);
    lint lastday=0;
    rep(i,N){
        plus.update_val(i,i+1,A[i]+T[i]-1);
        minus.update_val(i,i+1,T[i]-1);
    }
    for(auto e:qs){
        lint D=e.fi.fi,q=e.fi.se,L=e.se.fi,R=e.se.se;
        plus.add_val(0,N,-(D-lastday));
        minus.add_val(0,N,-(D-lastday));
        minus.update_max(0,N,0);
        plus.update_max(0,N,0);
        ans[q]=plus.query_sum(L,R)-minus.query_sum(L,R);
        lastday=D;
    }
    rep(i,Q) cout << ans[i] << endl;
}

yukicoder

結果

テストケース

ソースコード