Submission #1124002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124002		LucaIlie	Fire (JOI20_ho_t5)	C++20	1 / 100	1098 ms	55720 KiB

ho_t5

#include <bits/stdc++.h>

using namespace std;

struct query {
    int t, l, r;
    long long ans;
};

const int MAX_N = 2e5;
const int MAX_Q = 2e5;
int n;
int a[MAX_N + 1], leftt[MAX_N + 1], rightt[MAX_N + 1];
vector<int> queriesByTime[MAX_N + 1];
vector<int> stopIncreasingR[MAX_N + 1], startDecreasingL[MAX_N + 1], stopAll[MAX_N + 1];
query queries[MAX_Q];
set<int> increasingR, constantR, constantL, decreasingL;

long long getSumPrefix( int t, int p ) {
    //printf( "%d %d\n", t, p );
    long long sum = 0;
    for ( int i: increasingR )
        sum += (long long)min( i + t, p ) * a[i];
    for ( int i: constantR )
        sum += (long long)min( rightt[i] - 1, p ) * a[i];
    for ( int i: constantL )
        sum -= (long long)min( i - 1, p ) * a[i];
    for ( int i: decreasingL )
        sum -= (long long)min( t + leftt[i], p ) * a[i];
    return sum;
}

int main() {
    int q;

    cin >> n >> q;
    for ( int i = 1; i <= n; i++ )
        cin >> a[i];
    for ( int i = 0; i < q; i++ ) {
        cin >> queries[i].t >> queries[i].l >> queries[i].r;
        queriesByTime[queries[i].t].push_back( i );
    }

    vector<int> stack;
    for ( int i = 1; i <= n; i++ ) {
        while ( !stack.empty() && a[i] > a[stack.back()] )
            stack.pop_back();
        if ( !stack.empty() )
            leftt[i] = stack.back();
        else
            leftt[i] = -(n + 1);
        stack.push_back( i );
    }
    while ( !stack.empty() )
        stack.pop_back();
    for ( int i = n; i >= 1; i-- ) {
        while ( !stack.empty() && a[i] >= a[stack.back()] )
            stack.pop_back();
        if ( !stack.empty() )
            rightt[i] = stack.back();
        else
            rightt[i] = (n + 1);
        stack.push_back( i );
    }

    for ( int i = 1; i <= n; i++ ) {
        int goDown = i - leftt[i], goIncreasing = rightt[i] - i;
        increasingR.insert( i );
        constantL.insert( i );
        stopIncreasingR[goIncreasing].push_back( i );
        startDecreasingL[goDown].push_back( i );
        stopAll[goDown + goIncreasing - 1].push_back( i );
    }

    for ( int t = 1; t <= n; t++ ) {
        for ( int i: stopIncreasingR[t] ) {
            increasingR.erase( i );
            constantR.insert( i );
        }
        for ( int i: startDecreasingL[t] ) {
            constantL.erase( i );
            decreasingL.insert( i );
        }
        for ( int i: stopAll[t] ) {
            constantR.erase( i );
            decreasingL.erase( i );
        }

        /*printf( "timp\n" );
        for ( int i: increasingR )
            printf( "%d ", i );
        printf( "\n" );
        for ( int i: constantR )
            printf( "%d ", i );
        printf( "\n" );
        for ( int i: constantL )
            printf( "%d ", i );
        printf( "\n" );
        for ( int i: decreasingL )
            printf( "%d ", i );
        printf( "\n\n" );*/

        for ( int i: queriesByTime[t] ) {
            //printf( "query\n" );
            queries[i].ans = getSumPrefix( t, queries[i].r ) - getSumPrefix( t, queries[i].l - 1 );
        }
    }

    for ( int i = 0; i < q; i++ )
        cout << queries[i].ans << "\n";

    return 0;
}

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