Submission #540853

#	Time	Username	Problem	Language	Result	Execution time	Memory
540853		chonka	Food Court (JOI21_foodcourt)	C++98	100 / 100	437 ms	55036 KiB

foodcourt

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

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define MAXN 250007
int n , m , q ;

vector < pair < int , int > > v[ MAXN ] ;
vector < pair < int , long long > > to_query[ MAXN ] ;

int gr_col[ MAXN ] ;
bool qtype[ MAXN ] ;
long long ans[ MAXN ] ;

struct node {
    long long sm , mn ;
    node ( ) { sm = mn = 0 ; }
};

node unite ( node p1 , node p2 ) {
    node ret = node ( ) ;
    ret.sm = p1.sm + p2.sm ;
    ret.mn = min ( p1.mn , p1.sm + p2.mn ) ;
    return ret ;
}

class Tree {
public :
    node tr[ 4 * MAXN ] ;
    long long aux[ 4 * MAXN ] ;
    long long neg[ 4 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        tr[ where ] = node ( ) ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
    }
    void update ( int where , int IL , int IR , int pos , int add ) {
        if ( IR < pos || pos < IL ) { return ; }
        if ( IL == IR ) {
            tr[ where ].sm += add ;
            tr[ where ].mn = min ( 0LL , tr[ where ].sm ) ;
            aux[ where ] = max ( tr[ where ].sm , 0LL ) ;
            neg[ where ] = -tr[ where ].mn ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        if ( pos <= mid ) {
            update ( 2 * where , IL , mid , pos , add ) ;
        }
        else {
            update ( 2 * where + 1 , mid + 1 , IR , pos , add ) ;
        }
        tr[ where ] = unite ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
        aux[ where ] = aux[ 2 * where ] + aux[ 2 * where + 1 ] ;
        neg[ where ] = neg[ 2 * where ] + neg[ 2 * where + 1 ] ;
    }
    node query ( int where , int IL , int IR , int CURL , int CURR ) {
        if ( IL > IR || CURL > CURR ) { return node ( ) ; }
        if ( IR < CURL || CURR < IL ) { return node ( ) ; }
        if ( CURL <= IL && IR <= CURR ) { return tr[ where ] ; }
        int mid = ( IL + IR ) / 2 ;
        return unite ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
    }
    long long get_neg ( int where , int IL , int IR , int CURL , int CURR ) {
        if ( IL > IR || CURL > CURR ) { return 0 ; }
        if ( IR < CURL || CURR < IL ) { return 0 ; }
        if ( CURL <= IL && IR <= CURR ) { return neg[ where ] ; }
        int mid = ( IL + IR ) / 2 ;
        return get_neg ( 2 * where , IL , mid , CURL , CURR ) + get_neg ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ;
    }
    int get ( int where , int IL , int IR , long long cnt ) {
        if ( IL == IR ) { return gr_col[ IL ] ; }
        int mid = ( IL + IR ) / 2 ;
        if ( aux[ 2 * where ] >= cnt ) {
            return get ( 2 * where , IL , mid , cnt ) ;
        }
        else {
            return get ( 2 * where + 1 , mid + 1 , IR , cnt - aux[ 2 * where ] ) ;
        }
    }
};
Tree w ;

void input ( ) {
    cin >> n >> m >> q ;
    for ( int i = 1 ; i <= q ; ++ i ) {
        int type ;
        cin >> type ;
        if ( type == 1 ) {
            int l , r , k , c ;
            cin >> l >> r >> c >> k ;
            v[ l ].push_back ( { i , k } ) ;
            v[ r + 1 ].push_back ( { i , -k } ) ;
            gr_col[ i ] = c ;
        }
        else if ( type == 2 ) {
            int l , r , k ;
            cin >> l >> r >> k ;
            v[ l ].push_back ( { i , -k } ) ;
            v[ r + 1 ].push_back ( { i , k } ) ;
        }
        else {
            int l ;
            long long pos ;
            cin >> l >> pos ;
            to_query[ l ].push_back ( { i , pos } ) ;
            qtype[ i ] = true ;
        }
    }
}

void solve ( ) {
    w.init ( 1 , 1 , q ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( auto [ wh , add ] : v[ i ] ) {
            w.update ( 1 , 1 , q , wh , add ) ;
        }
        for ( auto [ wh , cnt ] : to_query[ i ] ) {
            node ret = w.query ( 1 , 1 , q , 1 , wh ) ;
            if ( ret.sm - ret.mn < cnt ) {
                ans[ wh ] = 0 ;
            }
            else {
                ans[ wh ] = w.get ( 1 , 1 , q , cnt + w.get_neg ( 1 , 1 , q , 1 , wh ) + ret.mn ) ;
            }
        }
    }
    for ( int i = 1 ; i <= q ; ++ i ) {
        if ( qtype[ i ] == true ) {
            cout << ans[ i ] << "\n" ;
        }
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ;
    // cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

Compilation message (stderr)

foodcourt.cpp: In function 'void solve()':
foodcourt.cpp:118:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |         for ( auto [ wh , add ] : v[ i ] ) {
      |                    ^
foodcourt.cpp:121:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |         for ( auto [ wh , cnt ] : to_query[ i ] ) {
      |                    ^

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11