Submission #295628

#	Time	Username	Problem	Language	Result	Execution time	Memory
295628		CaroLinda	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	2512 ms	524292 KiB

street_lamps

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("O2")


#define lp(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define debug //printf
#define tiii tuple<int,int,int>
#define mkt make_tuple
#define pii pair<int,int>
#define mk make_pair
#define ll long long
#define ff first
#define ss second

const int MAXN = 3e5+10 ;

using namespace std ;

struct SegNode
{

    vector<int> e , d , soma , lz ;

    int create()
    {
        e.pb(0);
        d.pb(0);
        lz.pb(0) ;
        soma.pb(0);
        return sz(e) - 1 ;
    }

    int m(int l, int r) { return (l+r)>>1 ; }

    void refresh(int pos, int l , int r)
    {
        soma[pos] += lz[pos] * (r-l+1) ;

        if(l==r) return (void)(lz[pos]=0) ;

        int aux ;

        if( !e[pos]) aux = create() , e[pos] = aux ;
        lz[ e[pos] ] += lz[pos] ;

        if(!d[pos]) aux = create() , d[pos] = aux ;
        lz[ d[pos] ] += lz[pos] ;

        lz[pos] = 0 ;

    }

    void upd(int pos, int l,int r, int beg, int en , int val)
    {

        debug("Updatando %d %d com %d\n" , beg, en ,val ) ;

        if(!pos) return ;

        if(lz[pos] != 0) refresh(pos,l,r) ;

        if( l > en || r < beg ) return ;
        if(l >= beg && r <= en)
        {
            lz[pos] += val ;
            refresh(pos,l,r) ;
            return ;
        }

        int aux ;

        if(!e[pos]) aux = create() , e[pos] = aux ;
            upd(e[pos] , l , m(l,r) , beg, en , val ) ;

        if(!d[pos]) aux = create() , d[pos] = aux ;
            upd(d[pos] , m(l,r)+1, r, beg, en , val ) ;

        soma[pos] = soma[ e[pos] ] + soma[ d[pos] ] ;

    }

    int qry(int pos, int l , int r, int k)
    {

        if(!pos) return 0 ;
        if(lz[pos] != 0) refresh(pos,l,r) ;

        debug("Estou em %d %d, procurando %d, e minha soma eh %d e minha lz eh %d\n" , l , r ,  k , soma[pos], lz[pos]) ;

        if(l==r) return soma[pos] ;

        int aux ;

        if( k <= m(l,r) )
        {
            if( e[pos] == 0 ) aux = create() , e[pos] = aux ;
            return qry( e[pos] , l ,m(l,r) , k ) ;
        }
        else
        {
            if( d[pos] == 0 ) aux = create() , d[pos] = aux ;
            return qry( d[pos] , m(l,r)+1, r , k) ;
        }

    }

};

struct Seg
{

    int n ;
    SegNode tree[MAXN*2] ;

    Seg() { for(int i = 0 ; i < MAXN*2 ; i++ ) tree[i].create() , tree[i].create() ; }

    void upd( int beg, int en, int l1, int l2, int toSum )
    {

        for(beg += n , en += n ; beg < en ; beg >>= 1 , en >>= 1 )
        {
            if(beg&1)
            {
                debug("Entrei em %d\n" , beg ) ;
                tree[beg].upd(1,1,n,l1,l2,toSum) ;
                beg++ ;
            }
            if(en&1)
            {
                en--;
                debug("Entrei em %d\n" , en ) ;
                tree[en].upd(1,1,n, l1, l2, toSum ) ;
            }
        }

    }

    int qry(int x, int y)
    {

        int tot = 0 ;

        for(x += n ; x >= 1 ; x >>= 1 )
        {
            int val =  tree[x].qry( 1 , 1 , n , y ) ;
            debug("Query em %d e %d, consegui %d\n" , x , y  ,val ) ;
            tot += val ;
        }

        return tot ;
    }

} seg ;

int N , Q ;
set<pii> intervalos ;
char str[MAXN] , q[MAXN] ;

int main()
{

    scanf("%d%d", &N , &Q ) ;
    scanf("%s", str ) ;

    str[N] = 0 ;
    N++;

    seg.n = N+1 ;

    for(int i = 0 ; i < N ; i++ )
    {

        int j = i ;
        while( j < N && str[j] == '1' ) j++ ;

        debug("Achei o intervalo %d %d\n" , i+1 , j+1 ) ;

        //O intervalo eh [i,j-1]
        intervalos.insert( mk(i+1,j+1) ) ;
        seg.upd( i,j+1 , i+1, j+1 , -1 ) ;

        i = j ;


    }

    for(int i = 1 ; i <= Q ; i++ )
    {
        scanf("%s", q ) ;

        if(q[0] == 'q')
        {

            int a , b , segQuery ;
            scanf("%d%d", &a, &b );

            segQuery = seg.qry(a-1, b) ;

            auto it = intervalos.upper_bound( mk(a,N+5) ) ;
            it-- ;

            if( it->ss >= b ) segQuery += i+1 ;

            printf("%d\n" , segQuery ) ;

        }

        else
        {
            int lamp ;
            scanf("%d", &lamp ) ;

            auto meContem = intervalos.upper_bound(mk(lamp,N+5)) ;
            meContem--;

            debug("Estou no intervalo %d %d\n" , meContem->ff, meContem->ss ) ;

            if( str[lamp-1] == '0' )
            {

                pii toInsert=*meContem ;
                auto prox = meContem ; prox++ ;

                toInsert.ss = prox->ss ;
                intervalos.erase(prox) ;

                meContem = intervalos.upper_bound(mk(lamp,N+5)) ; meContem-- ;
                intervalos.erase(meContem) ;

                intervalos.insert( toInsert ) ;
                seg.upd(toInsert.ff-1,lamp, lamp+1, toInsert.ss, -i-1 ) ;

                str[lamp-1] = '1' ;

            }

            else
            {

                pii toInsert1 = mk(meContem->ff,lamp) ;
                pii toInsert2 = mk(lamp+1, meContem->ss ) ;

                seg.upd(toInsert1.ff-1, toInsert1.ss, toInsert2.ff, toInsert2.ss , i) ;

                intervalos.erase( meContem ) ;
                intervalos.insert(toInsert1) ;
                intervalos.insert(toInsert2) ;

                str[lamp-1] = '0' ;

            }

        }

    }

}

/*
5 9
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
toggle 3
query 1 6
*/

Compilation message (stderr)

street_lamps.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
street_lamps.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O2")
      | 
street_lamps.cpp: In member function 'void SegNode::upd(int, int, int, int, int, int)':
street_lamps.cpp:63:15: warning: left operand of comma operator has no effect [-Wunused-value]
   63 |         debug("Updatando %d %d com %d\n" , beg, en ,val ) ;
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:63:49: warning: right operand of comma operator has no effect [-Wunused-value]
   63 |         debug("Updatando %d %d com %d\n" , beg, en ,val ) ;
      |                                                 ^~
street_lamps.cpp:63:53: warning: right operand of comma operator has no effect [-Wunused-value]
   63 |         debug("Updatando %d %d com %d\n" , beg, en ,val ) ;
      |                                                     ^~~
street_lamps.cpp: In member function 'int SegNode::qry(int, int, int, int)':
street_lamps.cpp:95:15: warning: left operand of comma operator has no effect [-Wunused-value]
   95 |         debug("Estou em %d %d, procurando %d, e minha soma eh %d e minha lz eh %d\n" , l , r ,  k , soma[pos], lz[pos]) ;
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:95:92: warning: right operand of comma operator has no effect [-Wunused-value]
   95 |         debug("Estou em %d %d, procurando %d, e minha soma eh %d e minha lz eh %d\n" , l , r ,  k , soma[pos], lz[pos]) ;
      |                                                                                            ^
street_lamps.cpp:95:97: warning: right operand of comma operator has no effect [-Wunused-value]
   95 |         debug("Estou em %d %d, procurando %d, e minha soma eh %d e minha lz eh %d\n" , l , r ,  k , soma[pos], lz[pos]) ;
      |                                                                                                 ^
street_lamps.cpp:95:109: warning: right operand of comma operator has no effect [-Wunused-value]
   95 |         debug("Estou em %d %d, procurando %d, e minha soma eh %d e minha lz eh %d\n" , l , r ,  k , soma[pos], lz[pos]) ;
      |                                                                                                             ^
street_lamps.cpp: In member function 'void Seg::upd(int, int, int, int, int)':
street_lamps.cpp:131:23: warning: left operand of comma operator has no effect [-Wunused-value]
  131 |                 debug("Entrei em %d\n" , beg ) ;
      |                       ^~~~~~~~~~~~~~~~
street_lamps.cpp:138:23: warning: left operand of comma operator has no effect [-Wunused-value]
  138 |                 debug("Entrei em %d\n" , en ) ;
      |                       ^~~~~~~~~~~~~~~~
street_lamps.cpp: In member function 'int Seg::qry(int, int)':
street_lamps.cpp:153:19: warning: left operand of comma operator has no effect [-Wunused-value]
  153 |             debug("Query em %d e %d, consegui %d\n" , x , y  ,val ) ;
      |                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:153:59: warning: right operand of comma operator has no effect [-Wunused-value]
  153 |             debug("Query em %d e %d, consegui %d\n" , x , y  ,val ) ;
      |                                                           ^
street_lamps.cpp:153:63: warning: right operand of comma operator has no effect [-Wunused-value]
  153 |             debug("Query em %d e %d, consegui %d\n" , x , y  ,val ) ;
      |                                                               ^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:183:15: warning: left operand of comma operator has no effect [-Wunused-value]
  183 |         debug("Achei o intervalo %d %d\n" , i+1 , j+1 ) ;
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:183:46: warning: right operand of comma operator has no effect [-Wunused-value]
  183 |         debug("Achei o intervalo %d %d\n" , i+1 , j+1 ) ;
      |                                             ~^~
street_lamps.cpp:223:19: warning: left operand of comma operator has no effect [-Wunused-value]
  223 |             debug("Estou no intervalo %d %d\n" , meContem->ff, meContem->ss ) ;
      |                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  169 |     scanf("%d%d", &N , &Q ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  170 |     scanf("%s", str ) ;
      |     ~~~~~^~~~~~~~~~~~
street_lamps.cpp:196:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  196 |         scanf("%s", q ) ;
      |         ~~~~~^~~~~~~~~~
street_lamps.cpp:202:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  202 |             scanf("%d%d", &a, &b );
      |             ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:218:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  218 |             scanf("%d", &lamp ) ;
      |             ~~~~~^~~~~~~~~~~~~~

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