Submission #1124010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124010		LucaIlie	Fire (JOI20_ho_t5)	C++20	1 / 100	721 ms	69012 KiB

ho_t5

#include <bits/stdc++.h>

using namespace std;

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

struct AIB {
    int n;
    vector<long long> aib;

    void init( int _n ) {
        n = _n;
        aib.resize( n + 1 );
    }

    void update( int i, long long x ) {
        while ( i <= n ) {
            aib[i] += x;
            i += (i & -i);
        }
    }

    long long query( int i ) {
        long long sum = 0;
        while ( i > 0 ) {
            sum += aib[i];
            i -= (i & -i);
        }
        return sum;
    }
};

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;
AIB sumIncreasingR, sumIncreasingRI;
AIB sumConstantR, sumConstantRI;
AIB sumConstantL, sumConstantLI;
AIB sumDecreasingL, sumDecreasingLI;

void toggleIncreasingR( int i ) {
    if ( increasingR.find( i ) == increasingR.end() ) {
        increasingR.insert( i );
        sumIncreasingR.update( i, a[i] );
        sumIncreasingRI.update( i, (long long)a[i] * i );
    } else {
        increasingR.erase( i );
        sumIncreasingR.update( i, -a[i] );
        sumIncreasingRI.update( i, -(long long)a[i] * i );
    }
}

void toggleConstantR( int i ) {
    if ( constantR.find( rightt[i] ) == constantR.end() ) {
        constantR.insert( rightt[i] );
        sumConstantR.update( rightt[i], a[i] );
        sumConstantRI.update( rightt[i], (long long)a[i] * (rightt[i] - 1) );
    } else {
        constantR.erase( rightt[i] );
        sumConstantR.update( rightt[i], -a[i] );
        sumConstantRI.update( rightt[i], -(long long)a[i] * (rightt[i] - 1) );
    }
}

void toggleConstantL( int i ) {
    if ( constantL.find( i ) == constantL.end() ) {
        constantL.insert( i );
        sumConstantL.update( i, a[i] );
        sumConstantLI.update( i, (long long)a[i] * i );
    } else {
        constantL.erase( i );
        sumConstantL.update( i, -a[i] );
        sumConstantLI.update( i, -(long long)a[i] * i );
    }
}

void toggleDecreasingL( int i ) {
    if ( decreasingL.find( leftt[i] ) == decreasingL.end() ) {
        decreasingL.insert( leftt[i] );
        sumDecreasingL.update( leftt[i], a[i] );
        sumDecreasingLI.update( leftt[i], (long long)a[i] * leftt[i] );
    } else {
        decreasingL.erase( leftt[i] );
        sumDecreasingL.update( leftt[i], -a[i] );
        sumDecreasingLI.update( leftt[i], -(long long)a[i] * leftt[i] );
    }
}

long long handleIncreasingR( int t, int p ) {
    auto ptr = increasingR.upper_bound( p - t );
    int pos = (ptr == increasingR.end() ? n + 1 : *ptr);
    long long sum = sumIncreasingRI.query( pos - 1 ) + sumIncreasingR.query( pos - 1 ) * t + (sumIncreasingR.query( n ) - sumIncreasingR.query( pos - 1 )) * p;
    return sum;
}

long long handleConstantR( int t, int p ) {
    auto ptr = constantR.upper_bound( p + 1 );
    int pos = (ptr == constantR.end() ? n + 2 : *ptr);
    long long sum = sumConstantRI.query( pos - 1 ) + (sumConstantR.query( n + 1 ) - sumConstantR.query( pos - 1 )) * p;
    return sum;
}

long long handleConstantL( int t, int p ) {
    auto ptr = constantL.upper_bound( p + 1 );
    int pos = (ptr == constantL.end() ? n + 1 : *ptr);
    long long sum = sumConstantLI.query( pos - 1 ) - sumConstantL.query( pos - 1 ) + (sumConstantL.query( n ) - sumConstantL.query( pos - 1 )) * p;
    return sum;
}

long long handleDecreasingL( int t, int p ) {
    auto ptr = decreasingL.upper_bound( p - t );
    int pos = (ptr == decreasingL.end() ? n + 1 : *ptr);
    long long sum = sumDecreasingLI.query( pos - 1 ) + sumDecreasingL.query( pos - 1 ) * t + (sumDecreasingL.query( n ) - sumDecreasingL.query( pos - 1 )) * p;
    return sum;
}

long long getSumPrefix( int t, int p ) {
    long long sum = 0;
    sum += handleIncreasingR( t, p );
    sum += handleConstantR( t, p );
    sum -= handleConstantL( t, p );
    sum -= handleDecreasingL( t, p );
    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 );
    }

    sumIncreasingR.init( n + 2 );
    sumIncreasingRI.init( n + 2 );
    sumConstantR.init( n + 2 );
    sumConstantRI.init( n + 2 );
    sumDecreasingL.init( n + 2 );
    sumDecreasingLI.init( n + 2 );
    sumConstantL.init( n + 2 );
    sumConstantLI.init( n + 2 );
    for ( int i = 1; i <= n; i++ ) {
        int goDown = i - leftt[i], goIncreasing = rightt[i] - i;
        toggleIncreasingR( i );
        toggleConstantL( 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] ) {
            toggleIncreasingR( i );
            toggleConstantR( i );
        }
        for ( int i: startDecreasingL[t] ) {
            toggleConstantL( i );
            toggleDecreasingL( i );
        }
        for ( int i: stopAll[t] ) {
            toggleConstantR( i );
            toggleDecreasingL( i );
        }

        for ( int i: queriesByTime[t] )
            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