oj.uz

Submission #501646

# Submission time Handle Problem Language Result Execution time Memory
501646 2022-01-04T09:11:25 Z balbit Fire (JOI20_ho_t5) C++14
100 / 100
 874 ms 115288 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}


const int maxn = 4e5+10;
struct act{
    int l, v;
};
struct seg{
    ll s[maxn*4], tg[maxn*4];
    void push(int o, int l, int r){
        if (tg[o]) {
            s[o] += tg[o] * (r-l+1);
            if (l!=r) {
                tg[o*2] += tg[o];
                tg[o*2+1] += tg[o];
            }
            tg[o] = 0;
        }
    }
    void MO(int L, int R, ll v, int o=1, int l=0, int r=maxn-1) {
        push(o,l,r);
        if (l>R || r<L) return;
        if (l >= L && r <= R) {
            tg[o] += v;
            push(o,l,r);
            return;
        }
        int mid = (l+r)/2;
        MO(L,R,v,o*2,l,mid);
        MO(L,R,v,o*2+1,mid+1,r);
        s[o] = (s[o*2]+ s[o*2+1]);
    }

    ll QU(int L, int R, int o=1, int l=0, int r=maxn-1) {
        push(o,l,r);
        if (l>R || r<L) return 0;
        if (l>=L && r<=R) {
            return s[o];
        }
        int mid = (l+r)/2;
        return (QU(L,R,o*2,l,mid)+ QU(L,R,o*2+1,mid+1,r));
    }

    void go(act A) {
        MO(max(A.l,0ll), maxn-1, A.v);
    }

    seg(){
        memset(s, 0, sizeof s);
        memset(tg, 0, sizeof tg);
    }
};

seg straight, slant;



vector<act> straighta[maxn], slanta[maxn];

void Tri(int a, int b, int v) {
    if (v == 0) return;
    bug("tri", a, b, v);

    int steps = b-a+1;
    straight.MO(b+1, maxn-1, -v);
    slant.MO(a, maxn-1, v);

    if (steps < maxn) {
        straighta[steps].pb({b+1, +v});
        slanta[steps].pb({a, -v});
    }
}

int lbig[maxn], rbig[maxn];
int a[maxn];

ll ask(int t, int l, int r) {
    ll str = straight.QU(l,r);
    ll sla = slant.QU(max(l-t,0ll), max(r-t,0ll));
    return str + sla;
}

ll ans[maxn];

struct que{
    int t, l, r, id;
};

signed main(){
    IOS();
    bug(1,2);
    int n; cin>>n;
    int q; cin>>q;
    REP(i,n) {
        cin>>a[i];
    }

    {
        vector<pii> yo; yo.pb({-n-2,inf}); // stuff on the left are bigger
        REP(i,n) {
            while (yo.back().s < a[i]) {
                yo.pop_back();
            }
            lbig[i] = yo.back().f;
            yo.pb({i, a[i]});
            bug(i, lbig[i]);
        }
    }

    {
        vector<pii> yo; yo.pb({n,inf}); // stuff on the left are bigger
        RREP(i,n) {
            while (yo.back().s <= a[i]) { // leq here
                yo.pop_back();
            }
            rbig[i] = yo.back().f;
            yo.pb({i, a[i]});
            bug(i, rbig[i]);
        }
    }

    REP(i,n) {
        int prv = lbig[i] + 1;
        int j = rbig[i] - 1;
        Tri(prv, j, a[i]);
        Tri(prv, i-1, -a[i]);
        Tri(i+1, j, -a[i]);
    }

    vector<que> bar;

    REP(i,q) {
        int t,l,r;
        cin>>t>>l>>r;
        --l; --r;
        bar.pb({t,l,r,i});
    }

    sort(ALL(bar), [&](que a, que b){return a.t < b.t;});

    int nat = -1;

    for (auto e : bar) {
        while (nat < e.t) {
            ++nat;
            bug(nat);
            for (act a : straighta[nat]) {
                bug("straight", a.l, a.v);
                straight.go(a);
            }
            for (act a : slanta[nat]) {
                bug(a.l, a.v);
                slant.go(a);
            }
        }

        ans[e.id] = ask(e.t, e.l, e.r);

    }

    REP(i,q) {
        cout<<ans[i]<<endl;
    }



}

/*
5 3
5 0 0 0 0
0 1 3
1 1 3
2 1 3
*/

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 69168 KB Output is correct
2 Correct 32 ms 69252 KB Output is correct
3 Correct 30 ms 69248 KB Output is correct
4 Correct 31 ms 69232 KB Output is correct
5 Correct 29 ms 69252 KB Output is correct
6 Correct 29 ms 69176 KB Output is correct
7 Correct 29 ms 69280 KB Output is correct
8 Correct 29 ms 69200 KB Output is correct
9 Correct 30 ms 69200 KB Output is correct
10 Correct 28 ms 69192 KB Output is correct
11 Correct 33 ms 69324 KB Output is correct
12 Correct 30 ms 69180 KB Output is correct
13 Correct 30 ms 69196 KB Output is correct
14 Correct 30 ms 69192 KB Output is correct
15 Correct 30 ms 69268 KB Output is correct
16 Correct 30 ms 69192 KB Output is correct
17 Correct 29 ms 69252 KB Output is correct
18 Correct 30 ms 69176 KB Output is correct
19 Correct 31 ms 69180 KB Output is correct
20 Correct 32 ms 69236 KB Output is correct
21 Correct 30 ms 69240 KB Output is correct
22 Correct 29 ms 69248 KB Output is correct
23 Correct 30 ms 69188 KB Output is correct
24 Correct 29 ms 69188 KB Output is correct
25 Correct 30 ms 69184 KB Output is correct
26 Correct 29 ms 69260 KB Output is correct
27 Correct 29 ms 69196 KB Output is correct
28 Correct 29 ms 69204 KB Output is correct
29 Correct 30 ms 69220 KB Output is correct
30 Correct 30 ms 69188 KB Output is correct
31 Correct 31 ms 69200 KB Output is correct
32 Correct 31 ms 69272 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 69168 KB Output is correct
2 Correct 766 ms 114228 KB Output is correct
3 Correct 750 ms 113928 KB Output is correct
4 Correct 809 ms 114328 KB Output is correct
5 Correct 778 ms 114704 KB Output is correct
6 Correct 819 ms 113996 KB Output is correct
7 Correct 775 ms 114668 KB Output is correct
8 Correct 795 ms 115108 KB Output is correct
9 Correct 766 ms 114888 KB Output is correct
10 Correct 740 ms 113920 KB Output is correct
11 Correct 746 ms 115072 KB Output is correct
12 Correct 719 ms 113844 KB Output is correct
13 Correct 807 ms 114592 KB Output is correct
14 Correct 780 ms 114160 KB Output is correct
15 Correct 782 ms 114628 KB Output is correct
16 Correct 805 ms 114092 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 69168 KB Output is correct
2 Correct 734 ms 113412 KB Output is correct
3 Correct 754 ms 112772 KB Output is correct
4 Correct 819 ms 113984 KB Output is correct
5 Correct 754 ms 112740 KB Output is correct
6 Correct 761 ms 113308 KB Output is correct
7 Correct 802 ms 113420 KB Output is correct
8 Correct 819 ms 113368 KB Output is correct
9 Correct 751 ms 113016 KB Output is correct
10 Correct 716 ms 112776 KB Output is correct
11 Correct 751 ms 114152 KB Output is correct
12 Correct 747 ms 113560 KB Output is correct
13 Correct 753 ms 114008 KB Output is correct
14 Correct 736 ms 113068 KB Output is correct
15 Correct 731 ms 113832 KB Output is correct
16 Correct 746 ms 113452 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 109492 KB Output is correct
2 Correct 785 ms 113212 KB Output is correct
3 Correct 813 ms 114176 KB Output is correct
4 Correct 784 ms 114068 KB Output is correct
5 Correct 829 ms 109424 KB Output is correct
6 Correct 816 ms 113080 KB Output is correct
7 Correct 862 ms 114324 KB Output is correct
8 Correct 835 ms 113664 KB Output is correct
9 Correct 796 ms 109712 KB Output is correct
10 Correct 833 ms 113872 KB Output is correct
11 Correct 800 ms 109808 KB Output is correct
12 Correct 806 ms 110036 KB Output is correct
13 Correct 789 ms 113048 KB Output is correct
14 Correct 790 ms 109700 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 69168 KB Output is correct
2 Correct 32 ms 69252 KB Output is correct
3 Correct 30 ms 69248 KB Output is correct
4 Correct 31 ms 69232 KB Output is correct
5 Correct 29 ms 69252 KB Output is correct
6 Correct 29 ms 69176 KB Output is correct
7 Correct 29 ms 69280 KB Output is correct
8 Correct 29 ms 69200 KB Output is correct
9 Correct 30 ms 69200 KB Output is correct
10 Correct 28 ms 69192 KB Output is correct
11 Correct 33 ms 69324 KB Output is correct
12 Correct 30 ms 69180 KB Output is correct
13 Correct 30 ms 69196 KB Output is correct
14 Correct 30 ms 69192 KB Output is correct
15 Correct 30 ms 69268 KB Output is correct
16 Correct 30 ms 69192 KB Output is correct
17 Correct 29 ms 69252 KB Output is correct
18 Correct 30 ms 69176 KB Output is correct
19 Correct 31 ms 69180 KB Output is correct
20 Correct 32 ms 69236 KB Output is correct
21 Correct 30 ms 69240 KB Output is correct
22 Correct 29 ms 69248 KB Output is correct
23 Correct 30 ms 69188 KB Output is correct
24 Correct 29 ms 69188 KB Output is correct
25 Correct 30 ms 69184 KB Output is correct
26 Correct 29 ms 69260 KB Output is correct
27 Correct 29 ms 69196 KB Output is correct
28 Correct 29 ms 69204 KB Output is correct
29 Correct 30 ms 69220 KB Output is correct
30 Correct 30 ms 69188 KB Output is correct
31 Correct 31 ms 69200 KB Output is correct
32 Correct 31 ms 69272 KB Output is correct
33 Correct 766 ms 114228 KB Output is correct
34 Correct 750 ms 113928 KB Output is correct
35 Correct 809 ms 114328 KB Output is correct
36 Correct 778 ms 114704 KB Output is correct
37 Correct 819 ms 113996 KB Output is correct
38 Correct 775 ms 114668 KB Output is correct
39 Correct 795 ms 115108 KB Output is correct
40 Correct 766 ms 114888 KB Output is correct
41 Correct 740 ms 113920 KB Output is correct
42 Correct 746 ms 115072 KB Output is correct
43 Correct 719 ms 113844 KB Output is correct
44 Correct 807 ms 114592 KB Output is correct
45 Correct 780 ms 114160 KB Output is correct
46 Correct 782 ms 114628 KB Output is correct
47 Correct 805 ms 114092 KB Output is correct
48 Correct 734 ms 113412 KB Output is correct
49 Correct 754 ms 112772 KB Output is correct
50 Correct 819 ms 113984 KB Output is correct
51 Correct 754 ms 112740 KB Output is correct
52 Correct 761 ms 113308 KB Output is correct
53 Correct 802 ms 113420 KB Output is correct
54 Correct 819 ms 113368 KB Output is correct
55 Correct 751 ms 113016 KB Output is correct
56 Correct 716 ms 112776 KB Output is correct
57 Correct 751 ms 114152 KB Output is correct
58 Correct 747 ms 113560 KB Output is correct
59 Correct 753 ms 114008 KB Output is correct
60 Correct 736 ms 113068 KB Output is correct
61 Correct 731 ms 113832 KB Output is correct
62 Correct 746 ms 113452 KB Output is correct
63 Correct 782 ms 109492 KB Output is correct
64 Correct 785 ms 113212 KB Output is correct
65 Correct 813 ms 114176 KB Output is correct
66 Correct 784 ms 114068 KB Output is correct
67 Correct 829 ms 109424 KB Output is correct
68 Correct 816 ms 113080 KB Output is correct
69 Correct 862 ms 114324 KB Output is correct
70 Correct 835 ms 113664 KB Output is correct
71 Correct 796 ms 109712 KB Output is correct
72 Correct 833 ms 113872 KB Output is correct
73 Correct 800 ms 109808 KB Output is correct
74 Correct 806 ms 110036 KB Output is correct
75 Correct 789 ms 113048 KB Output is correct
76 Correct 790 ms 109700 KB Output is correct
77 Correct 812 ms 114284 KB Output is correct
78 Correct 815 ms 114892 KB Output is correct
79 Correct 806 ms 114660 KB Output is correct
80 Correct 802 ms 114140 KB Output is correct
81 Correct 788 ms 114100 KB Output is correct
82 Correct 807 ms 114644 KB Output is correct
83 Correct 794 ms 114312 KB Output is correct
84 Correct 789 ms 113892 KB Output is correct
85 Correct 795 ms 114676 KB Output is correct
86 Correct 794 ms 114240 KB Output is correct
87 Correct 750 ms 115240 KB Output is correct
88 Correct 748 ms 114912 KB Output is correct
89 Correct 739 ms 113900 KB Output is correct
90 Correct 747 ms 115012 KB Output is correct
91 Correct 739 ms 110148 KB Output is correct
92 Correct 727 ms 113728 KB Output is correct
93 Correct 737 ms 110452 KB Output is correct
94 Correct 754 ms 115252 KB Output is correct
95 Correct 746 ms 115288 KB Output is correct
96 Correct 732 ms 114276 KB Output is correct
97 Correct 748 ms 114292 KB Output is correct
98 Correct 833 ms 113784 KB Output is correct
99 Correct 841 ms 114348 KB Output is correct
100 Correct 874 ms 114332 KB Output is correct
101 Correct 843 ms 109896 KB Output is correct
102 Correct 851 ms 114632 KB Output is correct