Submission #1122876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122876		LucaIlie	Fire (JOI20_ho_t5)	C++20	0 / 100	1097 ms	35116 KiB

ho_t5

#include <bits/stdc++.h>

using namespace std;

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

struct update {
    int i, j;
};

const int MAX_N = 2e5;
int a[MAX_N + 1];

struct range {
    int l, r, t;
    bool active = true;
    vector<int> pos;

    long long getSumPref( int tq, int rq ) {
        rq -= l - 1;
        int rep = min( rq, tq - t + 1 );
        long long sum = a[pos.back()] * rep;
        rq -= rep;
        for ( int i = pos.size() - 1; i >= 1; i-- ) {
            rep = min( rq, pos[i - 1] - pos[i] );
            //printf( "%d %d %d %d\n", tq, rq, pos[i], pos[i - 1] );
            sum += (long long)a[pos[i]] * rep;
            rq -= rep;
        }
        return sum;
    }

    long long getSumRange( int tq, int lq, int rq ) {
        lq = max( l, lq );
        rq = min( r, rq );
        return getSumPref( tq, rq ) - getSumPref( tq, lq - 1 );
    }

    void adopt( int tu, range &x ) {
        x.active = false;
        r = x.r;
        int p = pos.back();
        pos.clear();
        swap( x.pos, pos );
        pos.push_back( p );
        t = tu;
    }
};

vector<int> queriesByTime[MAX_N + 1];
vector<update> updatesByTime[MAX_N + 1];
range rangess[MAX_N + 1];
query queries[MAX_N + 1];

int main() {
    int n, 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;
        queries[i].index = i;
        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())
            updatesByTime[i - stack.back()].push_back( { stack.back(), i } );
        stack.push_back( i );
        rangess[i] = { i, i, 1, true, { i + 1, i } };
    }

    for ( int t = 1; t <= n; t++ ) {
        reverse( updatesByTime[t].begin(), updatesByTime[t].end() );
        for ( update u: updatesByTime[t] )
            rangess[u.i].adopt( t, rangess[u.j] );

        /*for ( int i = 1; i <= n; i++ ) {
            if ( rangess[i].active ) {
                printf( "lrt %d %d %d\n", rangess[i].l, rangess[i].r, rangess[i].t );
                for ( int j = rangess[i].pos.size() - 1; j >= 0; j-- )
                    printf( "%d ", rangess[i].pos[j] );
                printf( "\n" );
            }
        }
        printf( "\n" );*/

        for ( int i: queriesByTime[t] ) {
            int l = queries[i].l, r = queries[i].r;
            //printf( "QUERY %d\n", queries[i].index );
            for ( int j = 1; j <= n; j++ ) {
                if ( !rangess[j].active )
                    continue;
                if ( rangess[j].r < l || rangess[j].l > r )
                    continue;
                long long sum = rangess[j].getSumRange( t, l, r );;
                queries[i].ans += sum;
                //printf( "lrs %d %d %d\n", rangess[j].l, rangess[j].r, sum );
            }
        }
    }

    sort( queries, queries + q, []( query a, query b ) { return a.index < b.index; } );

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

    return 0;
}

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