oj.uz

Submission #295658

# Submission time Handle Problem Language Result Execution time Memory
295658 2020-09-09T19:39:38 Z CaroLinda Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 524292 KB 
#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)
    {

        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) ;

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

    }

};

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

SegNode tree[MAXN] ;

void upd(int pos, int l, int r, int toSum) { for(int i = pos ; i <= N ; i+=(i&-i)) tree[i].upd(1,1,N, l, r, toSum) ; }
int qry(int x , int y )
{
    int tot = 0 ;
    for(int i = x ; i > 0 ; i -= (i&-i)) tot += tree[i].qry(1,1,N, y) ;

    return tot ;
}

int main()
{

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

    str[N] = '0';
    N++;

    for(int i = 1 ; i <= N ; i++ )
    {
        tree[i].create() ;
        tree[i].create() ;
    }

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

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

        //O intervalo eh [i,j]
        intervalos.insert( mk(i+1,j+1) ) ;
        upd( i+1 , i+1, j+1, -1 ) ;
        upd(j+2, 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 = qry(a,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--;

            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 ) ;
                upd( toInsert.ff, lamp+1, toInsert.ss , -i-1 ) ;
                upd(lamp + 1 , lamp+1, toInsert.ss , i+1 ) ;

                str[lamp-1] = '1' ;

            }

            else
            {

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

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


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

                str[lamp-1] = '0' ;

            }

        }

    }

}

/*
1 3
0
query 1 2
toggle 1
query 1 2

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

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 function 'int main()':
street_lamps.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |     scanf("%d%d", &N , &Q ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |     scanf("%s", str ) ;
      |     ~~~~~^~~~~~~~~~~~
street_lamps.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |         scanf("%s", q ) ;
      |         ~~~~~^~~~~~~~~~
street_lamps.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  166 |             scanf("%d%d", &a, &b );
      |             ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:182:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  182 |             scanf("%d", &lamp ) ;
      |             ~~~~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28544 KB Output is correct
2 Correct 18 ms 28544 KB Output is correct
3 Correct 18 ms 28544 KB Output is correct
4 Correct 18 ms 28544 KB Output is correct
5 Correct 20 ms 28544 KB Output is correct
6 Correct 18 ms 28544 KB Output is correct
7 Correct 18 ms 28576 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 31156 KB Output is correct
2 Correct 685 ms 31376 KB Output is correct
3 Correct 1722 ms 39016 KB Output is correct
4 Execution timed out 5058 ms 422212 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 29568 KB Output is correct
2 Correct 35 ms 29696 KB Output is correct
3 Correct 33 ms 29688 KB Output is correct
4 Correct 23 ms 29344 KB Output is correct
5 Execution timed out 5093 ms 464156 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 29824 KB Output is correct
2 Correct 26 ms 29696 KB Output is correct
3 Correct 28 ms 29568 KB Output is correct
4 Correct 28 ms 29440 KB Output is correct
5 Runtime error 3767 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28544 KB Output is correct
2 Correct 18 ms 28544 KB Output is correct
3 Correct 18 ms 28544 KB Output is correct
4 Correct 18 ms 28544 KB Output is correct
5 Correct 20 ms 28544 KB Output is correct
6 Correct 18 ms 28544 KB Output is correct
7 Correct 18 ms 28576 KB Output is correct
8 Correct 493 ms 31156 KB Output is correct
9 Correct 685 ms 31376 KB Output is correct
10 Correct 1722 ms 39016 KB Output is correct
11 Execution timed out 5058 ms 422212 KB Time limit exceeded
12 Halted 0 ms 0 KB -