Submission #1126020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126020		LucaIlie	Street Lamps (APIO19_street_lamps)	C++20	20 / 100	3279 ms	220344 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

struct segment {
    int l, r, t;

    bool operator < ( const segment &s ) const {
        return l < s.l;
    }
};

struct query {
    int l, r;
};

struct AIB {
    int n;
    vector<int> aib, pos;

    void clear() {
        aib.clear();
        pos.clear();
        pos.push_back( -1 );
    }

    void insert( int x ) {
        pos.push_back( x );
    }

    void prep() {
        sort( pos.begin(), pos.end() );
        pos.resize( unique( pos.begin(), pos.end() ) - pos.begin() );
        n = pos.size();
        aib.resize( n );
    }

    void update( int i, int x ) {
        int l = 0, r = n;
        while ( r - l > 1 ) {
            int mid = (l + r) / 2;
            if ( pos[mid] < i )
                l = mid;
            else
                r = mid;
        }
        i = r;
        while ( i < n ) {
            aib[i] += x;
            i += (i & -i);
        }
    }

    int query( int i ) {
        if ( i < 0 )
            return 0;
        int l = 0, r = n;
        while ( r - l > 1 ) {
            int mid = (l + r) / 2;
            if ( pos[mid] > i )
                r = mid;
            else
                l = mid;
        }
        i = l;
        int x = 0;
        while ( i > 0 ) {
            x += aib[i];
            i -= (i & -i);
        }
        return x;
    }
};

const int MAX_N = 3e5;

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

    void init( int _n ) {
        n = _n;
        aib.resize( n + 1 );
        for ( int i = 0; i <= n; i++ )
            aib[i].clear();
    }

    void insert( int x, int y ) {
        int cx = x;
        while ( x > 0 ) {
            aib[x].insert( y );
            x -= (x & -x);
        }
        x = cx;
        while ( x <= n ) {
            aib[x].insert( y );
            x += (x & -x);
        }
    }

    void prep() {
        for ( int i = 0; i <= n; i++ )
            aib[i].prep();
    }

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

    int query( int i, int j ) {
        int x = 0;
        while ( i > 0 ) {
            x += aib[i].query( j );
            i -= (i & -i);
        }
        return x;
    }
};

const int MAX_Q = 3e5;
int n;
bool on[MAX_N];
vector<segment> insertSegments[MAX_Q + 1], eraseSegments[MAX_Q + 1];
vector<query> queries[MAX_Q + 1];
set<segment> activeSegments;
AIB2D erasedSegments;

void eraseSegment( segment s, int t ) {
    activeSegments.erase( s );
    erasedSegments.insert( s.l, s.l );
    erasedSegments.insert( s.l, s.r + 1 );
    erasedSegments.insert( s.r + 1, s.l );
    erasedSegments.insert( s.r + 1, s.r + 1 );
    eraseSegments[t].push_back( s );
}

void insertSegment( segment s, int t ) {
    //printf( "erase %d %d %d\n", t, s.l, s.r );
    activeSegments.insert( s );
    insertSegments[t].push_back( s );
}

int main() {
    cin.tie( nullptr );
    cout.tie( nullptr );
    ios_base::sync_with_stdio( false );

    int q;

    cin >> n >> q;
    for ( int i = 1; i <= n; i++ ) {
        char ch;
        cin >> ch;
        on[i] = (ch - '0');
    }

    erasedSegments.init( n + 1 );
    for ( int i = 1; i <= n; i++ ) {
        if ( !on[i] )
            continue;

        int j = i;
        while ( j <= n && on[j] )
            j++;

        insertSegment( { i, j - 1, 0 }, 0 );

        i = j - 1;
    }

    for ( int t = 1; t <= q; t++ ) {
        string type;
        cin >> type;
        if ( type == "query" ) {
            int l, r;
            cin >> l >> r;
            r--;
            queries[t].push_back( { l, r } );
            erasedSegments.insert( l, r );
        } else {
            int i;
            cin >> i;

            if ( !on[i] ) {
                on[i] = true;
                int l = i, r = i;
                if ( on[i - 1] ) {
                    auto p = activeSegments.lower_bound( { i, i, i } );
                    p--;
                    l = p->l;
                    eraseSegment( *p, t );
                }
                if ( on[i + 1] ) {
                    auto p = activeSegments.lower_bound( { i, i, i } );
                    r = p->r;
                    eraseSegment( *p, t );
                }
                insertSegment( { l, r, t }, t );
            } else {
                on[i] = false;
                auto p = activeSegments.upper_bound( { i, i, i } );
                p--;
                int l = p->l, r = p->r;
                eraseSegment( *p, t );
                if ( i > l )
                    insertSegment( { l, i - 1, t }, t );
                if ( i < r )
                    insertSegment( { i + 1, r, t }, t );
            }
        }
    }

    erasedSegments.prep();
    activeSegments.clear();
    for ( int t = 0; t <= q; t++ ) {
        for ( segment s: eraseSegments[t] ) {
            activeSegments.erase( s );
            erasedSegments.update( s.l, s.l, t - s.t );
            erasedSegments.update( s.l, s.r + 1, -(t - s.t) );
            erasedSegments.update( s.r + 1, s.l, -(t - s.t) );
            erasedSegments.update( s.r + 1, s.r + 1, t - s.t );
            //printf( "UPD %d %d %d\n", s.l, s.r, t - s.t );
        }
        for ( segment s: insertSegments[t] )
            activeSegments.insert( s );

        /*printf( "TIME %d\n", t );
        for ( segment s: activeSegments )
            printf( "%d %d %d\n", s.l, s.r, s.t );
        printf( "\n" );
        printf( "es\n" );
        for ( segment s: es )
            printf( "%d %d %d\n", s.l, s.r, s.t );
        printf( "\n" );*/

        for ( query q: queries[t] ) {
            int ans = erasedSegments.query( q.l, q.r );
            auto p = activeSegments.upper_bound( { q.l, q.l, q.l } );
            if ( p != activeSegments.begin() ) {
                p--;
                if ( p->l <= q.l && q.r <= p->r )
                    ans += t - p->t;
            }
            cout << ans << "\n";
        }

    }

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20