oj.uz

Submission #515796

# Submission time Handle Problem Language Result Execution time Memory
515796 2022-01-19T17:33:49 Z Jarif_Rahman Fire (JOI20_ho_t5) C++17
7 / 100
 1000 ms 56832 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

#define debug(s) for(auto x: s) cerr << x << " "; cerr << #s << "\n";

struct segtree{
    struct node{
        ll sm, lazy_sm;
        node(){
            sm = 0, lazy_sm = 0;
        }
        node(ll x){
            sm = x, lazy_sm = 0;
        }
        node operator+(node a){
            node rt;
            rt.sm = sm+a.sm;
            return rt;
        }
        void pushdown_from(node a, int sz){
            sm+=a.lazy_sm*sz;
            lazy_sm+=a.lazy_sm;
        }
    };
    int k;
    vector<node> v;
    segtree(int n){
        k = 1;
        while(k < n) k*=2;
        k*=2;
        v.resize(k, node());
    }
    void add(int l, int r, int nd, int a, int b, ll x){
        if(a > r || b < l) return;
        if(a >= l && b <= r){
            v[nd].sm+=(b-a+1)*x;
            v[nd].lazy_sm+=x;
            return;
        }
        int md = (a+b)/2;
        v[2*nd].pushdown_from(v[nd], md-a+1);
        v[2*nd+1].pushdown_from(v[nd], b-md);
        v[nd].lazy_sm = 0;
        add(l, r, 2*nd, a, md, x);
        add(l, r, 2*nd+1, md+1, b, x);
        v[nd] = v[2*nd]+v[2*nd+1];
    }
    void add(int l, int r, int x){
        add(l, r, 1, 0, k/2-1, x);
    }
    ll sum(int l, int r, int nd, int a, int b){
        if(a > r || b < l) return 0;
        if(a >= l && b <= r) return v[nd].sm;
        int md = (a+b)/2;
        v[2*nd].pushdown_from(v[nd], md-a+1);
        v[2*nd+1].pushdown_from(v[nd], b-md);
        v[nd].lazy_sm = 0;
        int rt = sum(l, r, 2*nd, a, md) + sum(l, r, 2*nd+1, md+1, b);
        v[nd] = v[2*nd]+v[2*nd+1];
        return rt;
    }
    ll sum(int l, int r){
        return sum(l, r, 1, 0, k/2-1);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q; cin >> n >> q;
    vector<ll> s(n);
    for(ll &x: s) cin >> x;

    vector<int> prev(n, -1);
    stack<int> st;
    for(int i = n-1; i >= 0; i--){
        while(!st.empty() && s[i] > s[st.top()]) prev[st.top()] = i, st.pop();
        st.push(i);
    }
    while(!st.empty()) st.pop();

    vector<vector<int>> end(n+1);
    vector<vector<pair<int, int>>> chng(n+1);
    for(int i = 0; i < n; i++){
        while(!st.empty() && s[st.top()] <= s[i]){
            int x = st.top();
            st.pop();
            end[i-x-1].pb(x);
            if(prev[x] == -1) continue;
            if(s[prev[x]] <= s[i]) continue;
            chng[i-prev[x]-1].pb({prev[x], i});
        }
        st.push(i);
    }
    while(!st.empty()) end[n-st.top()-1].pb(st.top()), st.pop();

    vector<vector<array<int, 3>>> queries(n);
    for(int i = 0; i < q; i++){
        int t, l, r; cin >> t >> l >> r; t--, l--, r--;
        queries[t].pb({l, r, i});
    }

    vector<ll> ans(q, 0);
    segtree ss(n), s1(n), s2(n);
    for(int i = 0; i < n; i++) ss.add(i, i, s[i]);
    for(int i = 0; i+1 < n; i++) s1.add(i, i, max(0LL, s[i]-s[i+1]));

    for(int t = 1; t <= n; t++){
        for(int in: end[t-1]){
            ll x = s1.sum(in, in);
            if(in != n-1) ss.add(in+1, in+t-1, x);
            s1.add(in, in, -x);
        }
        for(auto [in, nxt]: chng[t-1]){
            ll x = s1.sum(in, in);
            ll y = x-(s[in]-s[nxt]);
            ss.add(in+1, nxt-1, y);
            s1.add(in, in, (s[in]-s[nxt])-x);
        }
        for(auto [l, r, in]: queries[t-1]){
            ans[in]+=ss.sum(l, r);

            int mx, a, b;
            if(t <= r-l+1){
                mx = t;
                a = l, b = r-mx+1;
                a--, b--;
                a = max(a, 0);
            }
            else{
                mx = r-l+1;
                a = r-t+1, b = l;
                a--, b--;
                a = max(a, 0);
            }

            ans[in]+=s1.sum(a, b)*mx;
            for(int i = a-1, c = mx-1; i >= 0 && c > 0; i--, c--) ans[in]+=s1.sum(i, i)*c;
            for(int i = b+1, c = mx-1; i < n && c > 0; i++, c--) ans[in]+=s1.sum(i, i)*c;
        }
    }

    for(ll x: ans) cout << x << "\n";
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Execution timed out 1100 ms 46656 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 595 ms 50580 KB Output is correct
3 Correct 623 ms 55680 KB Output is correct
4 Correct 616 ms 56832 KB Output is correct
5 Correct 585 ms 55864 KB Output is correct
6 Correct 669 ms 56232 KB Output is correct
7 Correct 608 ms 56240 KB Output is correct
8 Correct 623 ms 56136 KB Output is correct
9 Correct 604 ms 55828 KB Output is correct
10 Correct 599 ms 55540 KB Output is correct
11 Correct 645 ms 56732 KB Output is correct
12 Correct 605 ms 56236 KB Output is correct
13 Correct 622 ms 56540 KB Output is correct
14 Correct 606 ms 55872 KB Output is correct
15 Correct 608 ms 56624 KB Output is correct
16 Correct 610 ms 56104 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 47824 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -