답안 #515911

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
515911 2022-01-20T06:12:39 Z Jarif_Rahman Fire (JOI20_ho_t5) C++17
7 / 100
1000 ms 39436 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 BIT{
    int n;
    vector<ll> sm;
    BIT(int _n){
        n = _n;
        sm.resize(n);
    }
    void add(int in, int x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    ll sum(int in){
        in++;
        ll s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
    ll sum(int l, int r){
        return sum(r)-(l == 0? 0:sum(l-1));
    }
    void assign(int in, ll x){
        add(in, x-sum(in, in));
    }
};

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;
        ll 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);
    BIT s1(n), s2(n);
    for(int i = 0; i < n; i++) ss.add(i, i, s[i]);
    vector<ll> sth(n, 0);

    for(int i = 0; i+1 < n; i++) sth[i] = max(0LL, s[i]-s[i+1]);
    for(int i = 0; i+1 < n; i++){
        s1.assign(i, max(0LL, s[i]-s[i+1]));
        s2.assign(i, max(0LL, s[i]-s[i+1])*i);
    }

    for(int t = 1; t <= n; t++){
        for(int in: end[t-1]){
            if(in != n-1) ss.add(in+1, in+t-1, sth[in]);
            s1.assign(in, 0);
            s2.assign(in, 0);
            sth[in] = 0;
        }
        for(auto [in, nxt]: chng[t-1]){
            ll x = sth[in]-(s[in]-s[nxt]);
            ss.add(in+1, nxt-1, x);
            sth[in] = (s[in]-s[nxt]);
            s1.assign(in, s[in]-s[nxt]);
            s2.assign(in, (s[in]-s[nxt])*in);
        }
        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;

            if(mx != 1){
                //for(int i = a-1, c = mx-1; i >= 0 && c > 0; i--, c--) ans[in]+=sth[i]*c;
                for(int i = b+1, c = mx-1; i < n && c > 0; i++, c--) ans[in]+=sth[i]*c;
                int aa = max(0, a-mx+1);
                ll c = s1.sum(aa, a-1)+(s2.sum(aa, a-1)*(mx+1-a));
                ans[in]+=c;
            }
        }
    }

    for(ll x: ans) cout << x << "\n";
}
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Execution timed out 1093 ms 34768 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 393 ms 38724 KB Output is correct
3 Correct 472 ms 38276 KB Output is correct
4 Correct 429 ms 39436 KB Output is correct
5 Correct 387 ms 38500 KB Output is correct
6 Correct 401 ms 38784 KB Output is correct
7 Correct 427 ms 38872 KB Output is correct
8 Correct 434 ms 38684 KB Output is correct
9 Correct 434 ms 38504 KB Output is correct
10 Correct 412 ms 38200 KB Output is correct
11 Correct 421 ms 39288 KB Output is correct
12 Correct 403 ms 38900 KB Output is correct
13 Correct 422 ms 39048 KB Output is correct
14 Correct 412 ms 38416 KB Output is correct
15 Correct 408 ms 39192 KB Output is correct
16 Correct 441 ms 38932 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1089 ms 35892 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 -