Submission #206547

#	Time	Username	Problem	Language	Result	Execution time	Memory
206547		osaaateiasavtnl	Fire (JOI20_ho_t5)	C++14	100 / 100	412 ms	90832 KiB

ho_t5

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
 
const int N = 2e5 + 7;
int n, q, a[N], l[N], r[N];
vector <int> d[N];
vector <ii> mem[N], meml[N];
 
void add(int l, int r, int i, int x) {
    mem[l].app(mp(i, x));
    mem[r + 1].app(mp(i, -x));    
}   
void addl(int l, int r, int i, int x) {
    meml[l].app(mp(i, x));
    meml[r + 1].app(mp(i, -x));
}   
 
int link_l[N], link_r[N];
int ans[N];
 
struct Fen {
int f[N];
void clear() {
    for (int i = 0; i < N; ++i) f[i] = 0;
}   
void add(int i, int x) {
    for (; i < N; i |= i + 1) 
        f[i] += x;
}   
int get(int i) {
    int ans = 0;
    for (; i >= 0; i &= i + 1, --i) ans += f[i];
    return ans;
}   
int get(int l, int r) {
    return get(r) - get(l - 1);
}   
} f, fl;
 
int pref_mx[N], pref_sum[N];
//bigger left, not less right
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pref_mx[i + 1] = max(pref_mx[i], a[i]);
        pref_sum[i + 1] = pref_sum[i] + pref_mx[i + 1];
    }
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t >> l[i] >> r[i];
        --l[i]; --r[i];
        d[t + 1].app(i);
    }   
    vector <int> s;
    for (int i = 0; i < n; ++i) {
        while (s.size() && a[s.back()] <= a[i]) {
            link_r[s.back()] = i;
            s.pop_back();
        }   
        s.app(i);                    
    }   
    for (int e : s)
        link_r[e] = n;
    s.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (s.size() && a[s.back()] < a[i]) {
            link_l[s.back()] = i;
            s.pop_back();
        }   
        s.app(i);
    }   
    for (int e : s)
        link_l[e] = -1;
    s.clear();
    for (int i = 0; i < n; ++i) {
        if (link_r[i] - i < i - link_l[i]) {
            for (int j = i; j < link_r[i]; ++j) {
                int len1 = j - i + 1;
                int len2 = j - link_l[i];
                add(len1, len2, j, a[i]);
            }   
        }
        else {
            for (int j = link_l[i] + 1; j <= i; ++j) {
                int len1 = i - j + 1;
                int len2 = link_r[i] - j;
                if (link_r[i] == n)
                    len2 = N - 2;
                addl(len1, len2, j, a[i]);
            }            
        }   
    }   
 
    f.clear();
    fl.clear();
    for (int len = 1; len < N; ++len) {
        for (auto e : mem[len]) 
            f.add(e.f, e.s);
        for (auto e : meml[len]) {
            fl.add(e.f, e.s);
        }
        for (auto e : d[len]) {
            ans[e] += f.get(l[e], r[e]);
            if (l[e] + 1 < len) {
                int t = min(len - 1, r[e] + 1);
                ans[e] += pref_sum[t] - pref_sum[l[e]];   
                l[e] = t;
            }   
            if (l[e] <= r[e])
                ans[e] += fl.get(l[e] - len + 1, r[e] - len + 1);
        }
    }   
    for (int i = 0; i < q; ++i)
        cout << ans[i] << '\n';
}   

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80