Submission #1122891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122891		LucaIlie	Fire (JOI20_ho_t5)	C++20	0 / 100	1098 ms	45076 KiB

ho_t5

#include <bits/stdc++.h>

#define int long long

using namespace std;

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

struct update {
    int i, j;
};

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

struct DSU {
    vector<int> parent;

    void init( int n ) {
        parent.resize( n );
        for ( int v = 0; v < n; v++ )
            parent[v] = v;
    }

    int findParent( int v ) {
        if ( parent[v] == v )
            return v;
        parent[v] = findParent( parent[v] );
        return parent[v];
    }

    int unionn( int u, int v ) {
        u = findParent( u );
        v = findParent( v );
        parent[v] = u;
    }
};

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 + 1 );
        long long sum = (long long)a[pos.back()] * rep;
        rq -= rep;
        for ( int i = pos.size() - 2; i >= 0; i-- ) {
            rep = min( rq, pos[i] - pos[i + 1] );
            //printf( "%d %d %d %d %d\n", tq, rq, pos[i], pos[i + 1], sum );
            sum += (long long)a[pos[i]] * rep;
            rq -= rep;
        }
        //printf( "%d\n", sum );
        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];
DSU rngs;

signed 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 } };
    }

    rngs.init( n + 1 );
    for ( int t = 1; t <= n; t++ ) {
        reverse( updatesByTime[t].begin(), updatesByTime[t].end() );
        for ( update u: updatesByTime[t] ) {
            rangess[rngs.findParent( u.i )].adopt( t, rangess[rngs.findParent( u.j )] );
            rngs.unionn( u.i, 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 g %d %d\n", queries[i].index, l, r );
            for ( int j = 1; j <= n; j++ ) {
                if ( !rangess[j].active )
                    continue;
                //printf( "kof %d %d\n", rangess[j].l, rangess[j].r );
                if ( rangess[j].r < l || rangess[j].l > r )
                    continue;
                long long sum = rangess[j].getSumRange( t, l, r );
                //printf( "lrs %d %d %d\n", rangess[j].l, rangess[j].r, sum );
                queries[i].ans += 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;
}

Compilation message (stderr)

ho_t5.cpp: In member function 'long long int DSU::unionn(long long int, long long int)':
ho_t5.cpp:39:5: warning: no return statement in function returning non-void [-Wreturn-type]
   39 |     }
      |     ^

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