Submission #267041

#	Time	Username	Problem	Language	Result	Execution time	Memory
267041		Hideo	Fire (JOI20_ho_t5)	C++11	0 / 100	1090 ms	49948 KiB

ho_t5

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define pii pair < int, pi >
#define next next123
#define add add123

const int N = 2e5 + 7;
const int INF = 1e9 + 7;

pair < pi, pi > qr[N];
ll s[4][4 * N], v3[4 * N], lz[4 * N], ans[N];
int next[N], prv[N], con[N];
int a[N];
int n, q, t;

vector < pi > event[N];

void push (int v, int l, int r){
    if (l != r){
        lz[v + v] += lz[v];
        lz[v + v + 1] += lz[v];
    }
    v3[v] -= s[3][v] * lz[v];
    lz[v] = 0;
}

void del (int v, int l, int r, int pos, int type){
    push(v, l, r);
    if (l == r){
        s[type][v] = 0;
        if (type == 3)
            v3[v] = 0;
    }
    else {
        int mid = (l + r) >> 1;
        if (pos <= mid)
            del(v + v, l, mid, pos, type);
        else
            del(v + v + 1, mid + 1, r, pos, type);
        s[type][v] = s[type][v + v] + s[type][v + v + 1];
        v3[v] = v3[v + v] + v3[v + v + 1];
    }
}

void add (int v, int l, int r, int pos, int type){
    push(v, l, r);
    if (l == r){
        if (type == 3){
            s[3][v] = a[l];
            v3[v] = max(s[1][v], s[2][v]);
            if (!v3[v])
                v3[v] = s[0][v] * t;
        }
        else
            s[type][v] = 1LL * a[pos] * t;
    }
    else {
        int mid = (l + r) >> 1;
        if (pos <= mid)
            add(v + v, l, mid, pos, type);
        else
            add(v + v + 1, mid + 1, r, pos, type);
        s[type][v] = s[type][v + v] + s[type][v + v + 1];
        v3[v] = v3[v + v] + v3[v + v + 1];
    }
}

int srch (int v, int l, int r, int type){
    if (l == r)
        return l;
    else {
        int mid = (l + r) >> 1;
        if (s[type][v + v])
            return srch(v + v, l, mid, type);
        return srch(v + v + 1, mid + 1, r, type);
    }
}

pi srch2 (int v, int l, int r){
    if (l == r){
        if (s[1][v])
            return {l, 1};
        else
            return {l, 3};
    }
    int mid = (l + r) >> 1;
    if (max(s[1][v + v + 1], s[3][v + v + 1]))
        return srch2(v + v + 1, mid + 1, r);
    return srch2(v + v, l, mid);
}

int get_02 (int v, int l, int r, int ql, int qr, int type){
    if (ql <= l && r <= qr){
        if (s[type][v])
            return srch(v, l, r, type);
        return n + 1;
    }
    if (r < ql || qr < l)
        return n + 1;
    int mid = (l + r) >> 1;
    return min(get_02(v + v, l, mid, ql, qr, type), get_02(v + v + 1, mid + 1, r, ql, qr, type));
}

pi get_13 (int v, int l, int r, int ql, int qr){
    push(v, l, r);
    if (ql <= l && r <= qr){
        if (max(s[1][v], s[3][v]))
            return srch2(v, l, r);
        return {0, 0};
    }
    if (r < ql || qr < l)
        return {0, 0};
    int mid = (l + r) >> 1;
    return max(get_13(v + v, l, mid, ql, qr), get_13(v + v + 1, mid + 1, r, ql, qr));
}

void build (int v, int l, int r){
    if (l == r)
        s[0][v] = a[l];
    else {
        int mid = (l + r) >> 1;
        build(v + v, l, mid);
        build(v + v + 1, mid + 1, r);
        s[0][v] = s[0][v + v] + s[0][v + v + 1];
    }
}

ll get (int v, int l, int r, int ql, int qr){
    push(v, l, r);
    if (ql <= l && r <= qr)
        return s[0][v] * (t + 1) + s[1][v] + s[2][v] + v3[v];
    if (r < ql || qr < l)
        return 0LL;
    int mid = (l + r) >> 1;
    return get(v + v, l, mid, ql, qr) + get(v + v + 1, mid + 1, r, ql, qr);
}

main(){
    cin >> n >> q;
    stack < int > st;
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        while (!st.empty() && a[st.top()] <= a[i]){
            next[st.top()] = i;
            st.pop();
        }
        if (!st.empty())
            prv[i] = st.top();
        st.push(i);
    }
    for (int i = 1; i <= n; i++){
        if (!next[i])
            next[i] = n + 1;
        if (!prv[i])
            prv[i] = i - N + 4;
        if (next[i] - i < i - prv[i]){
            event[next[i] - i].pb(mk(1, i));
            event[i - prv[i]].pb(mk(3, i));
        }
        else if (next[i] - i > i - prv[i]){
            event[i - prv[i]].pb(mk(2, i));
            event[next[i] - i].pb(mk(3, i));
        }
        else
            event[i - prv[i]].pb(mk(3, i));
        if (prv[i] != i - N + 4)
            event[next[i] - prv[i] - 1].pb(mk(4, i));
    }
    for (int i = 1; i <= q; i++){
        scanf("%d%d%d", &qr[i].fr.fr, &qr[i].sc.fr, &qr[i].sc.sc);
        qr[i].fr.sc = i;
    }
    sort(qr + 1, qr + q + 1);
    int i = 1;
    build(1, 0, n);
    for (t = 1; t <= n; t++){
        for (pi it : event[t]){
            if (it.fr != 4)
                add(1, 0, n, it.sc, it.fr);
            del(1, 0, n, it.sc, con[it.sc]);
            con[it.sc] = it.fr;
        }
        lz[1]++;
        ll s1, s2;
        pi temp;
        while (qr[i].fr.fr == t){
            temp.fr = get_02(1, 0, n, max(0, qr[i].sc.fr - t - 1), qr[i].sc.fr - 1, 0);
            if (temp.fr == n + 1){
                temp.fr = get_02(1, 0, n, max(0, qr[i].sc.fr - t - 1), qr[i].sc.fr - 1, 2);
                if (temp.fr == n + 1){
                    temp = get_13(1, 0, n, max(0, qr[i].sc.fr - t - 1), qr[i].sc.fr - 1);
                    s1 = get(1, 0, n, 0, temp.fr) - 1LL * a[temp.fr] * (next[temp.fr] - qr[i].sc.fr);
                }
                else
                    s1 = get(1, 0, n, 0, temp.fr) - 1LL * a[temp.fr] * (temp.fr + t - qr[i].sc.fr + 1);
            }
            else
                s1 = get(1, 0, n, 0, temp.fr) - 1LL * a[temp.fr] * (temp.fr + t - qr[i].sc.fr + 1);
            swap(qr[i].sc.fr, qr[i].sc.sc);
            qr[i].sc.fr++;
            temp.fr = get_02(1, 0, n, max(0, qr[i].sc.fr - t - 1), qr[i].sc.fr - 1, 0);
            if (temp.fr == n + 1){
                temp.fr = get_02(1, 0, n, max(0, qr[i].sc.fr - t - 1), qr[i].sc.fr - 1, 2);
                if (temp.fr == n + 1){
                    temp = get_13(1, 0, n, max(0, qr[i].sc.fr - t - 1), qr[i].sc.fr - 1);
                    s2 = get(1, 0, n, 0, temp.fr) - 1LL * a[temp.fr] * (next[temp.fr] - qr[i].sc.fr);
                }
                else
                    s2 = get(1, 0, n, 0, temp.fr) - 1LL * a[temp.fr] * (temp.fr + t - qr[i].sc.fr + 1);
            }
            else
                s2 = get(1, 0, n, 0, temp.fr) - 1LL * a[temp.fr] * (temp.fr + t - qr[i].sc.fr + 1);
            if (qr[i].sc.sc == 1)
                s1 = 0;
            ans[qr[i].fr.sc] = s2 - s1;
            i++;
        }
    }
    for (int i = 1; i <= q; i++)
        printf("%lld\n", ans[i]);
}

Compilation message (stderr)

ho_t5.cpp:151:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  151 | main(){
      |      ^
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  155 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
ho_t5.cpp:183:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  183 |         scanf("%d%d%d", &qr[i].fr.fr, &qr[i].sc.fr, &qr[i].sc.sc);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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