oj.uz

답안 #1064601

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1064601 2024-08-18T15:20:21 Z _8_8_ Fire (JOI20_ho_t5) C++17
0 / 100
 266 ms 35160 KB 
#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 4e5 + 12, MOD = (int)1e9 + 7;

int n,q,s[N];
struct fenw{
    vector<ll> t;
    void init(int n_) {
        t.resize(n_+3);
    }
    void upd(int pos,ll val) {
        while(pos <= n) {
            t[pos] += val;
            pos += (pos & -pos);
        }
    }
    ll get(int i){
        ll ret =0;
        while(i) {
            ret += t[i];
            i -= i & -i;
        }
        return ret;
    }
    ll get(int l,int r) {
        if(!l) return get(r);
        return get(r) - get(l - 1);
    }
};
fenw x,y;
ll t[N * 4], sum[N * 4], cmin[N * 4], cmax[N * 4], add[N * 4];

void assign(int v,ll val) {
    add[v] += val;
    cmin[v] += val;cmax[v] += val;
    sum[v] += t[v] * val;
}
void push(int v) {
    if(add[v]) {
        assign(v + v,add[v]);
        assign(v + v + 1,add[v]);
        add[v] = 0;
    }
}
void merge(int v) {
    sum[v] = sum[v + v] + sum[v + v + 1];
    cmin[v] = min(cmin[v + v],cmin[v + v + 1]);
    cmax[v] = max(cmax[v + v],cmax[v + v + 1]);
    t[v] = t[v + v] + t[v + v + 1];
}
void upd(int l,int r,int v = 1,int tl = 0,int tr = n ) {
    if(l > r || tl > r || l > tr) return;
    if(tl >= l && tr <= r) {
        assign(v,1);
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        upd(l,r,v+v,tl,tm);
        upd(l,r,v + v + 1,tm + 1,tr);
        merge(v);
    }
}
void upd1(int pos,ll val,int v = 1,int tl = 0,int tr = n) {
    if(tl == tr) {
        sum[v] = t[v] = val;
        cmax[v] = cmin[v] = 1;
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd1(pos,val,v+v,tl,tm);
        else upd1(pos,val,v+v+1,tm+1,tr);
        merge(v);
    }
}
ll C[N];

ll get(int l,int r,int t_,int v = 1,int tl = 0,int tr = n) {
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r && tl == tr) {
        ll cost = max(0ll,min(t_ - C[tl]+1,cmin[v]));
        // cout << tl << ' ' << cost << '\n';
        return cost * 1ll * t[v];
        if(cmax[v] <= t_) {
            return sum[v];
        }   
        if(cmin[v] >= t_) {
            cout << tl << ' ' << tr << " " << cmin[v] << " " << t[v] << '\n';
            return t[v] * 1ll * t_;
        }
    }
    push(v);
    int tm = (tl + tr) >> 1;
    return get(l,r,t_,v+v,tl,tm) + get(l,r,t_,v+v+1,tm+1,tr);
}
ll find(int pos,int v = 1,int tl = 0,int tr = n) {
    if(tl == tr) {
        assert(cmax[v] == cmin[v]);
        return cmax[v];
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        ll ret;
        if(pos <= tm) ret = find(pos,v + v,tl,tm);
        else ret = find(pos,v + v + 1,tm + 1,tr);
        return ret;
    }
}
ll ans[N],w[N],pref[N];
vector<array<int,2>> qr[N];
void test() {
    cin >> n >> q;
    for(int i = 1;i <= n;i++) {
        cin >> s[i];
        pref[i] = pref[i - 1] + s[i];
    }
    for(int i = 1;i <= q;i++) {
        int l,r,t_;
        cin >> t_ >> l >> r;
        ans[i] += pref[r] - pref[l - 1];
        qr[r].push_back({t_,i});
        qr[l - 1].push_back({t_,i + q});
    }
    x.init(n);
    y.init(n);
    vector<int> st;
    for(int i = 1;i <= n;i++) {
        while(!st.empty() && s[st.back()] <= s[i]) {
            int j = st.back(),id = (int)st.size() - 1;
            int c = find(id);
            x.upd(c,w[j]);
            y.upd(c,c*1ll*w[j]);
            st.pop_back();
        }
        if((int)st.size()) {
            w[i] = s[st.back()] - s[i];
            C[(int)st.size()] = i - st.back();
        }
        upd(0,(int)st.size() - 1);
        upd1((int)st.size(),w[i]);
        st.push_back(i);
        for(auto [t_,id]:qr[i]) {
            // cout << get(0,(int(st.size()-1,t_) << "x\n";
            ans[id] += get(0,(int)st.size()-1,t_) + x.get(t_ + 1,n) * 1ll * t_ + y.get(0,t_);
        }
    }
    for(int i = 1;i <= q;i++) {
        cout << ans[i] - ans[i + q] << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Incorrect 5 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 266 ms 35156 KB Output is correct
3 Correct 246 ms 35084 KB Output is correct
4 Incorrect 242 ms 35160 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Incorrect 260 ms 34644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 196 ms 31572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Incorrect 5 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -