oj.uz

답안 #300074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
300074 2020-09-16T12:07:10 Z mohamedsobhi777 가로등 (APIO19_street_lamps) C++14
20 / 100
 5000 ms 9108 KB 
#include<bits/stdc++.h>

/*
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")*/

#define I inline void 
#define S struct 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 1e5 + 7 , mod = 1e9 + 7 ; 
const int inf = N ; 
// How interesting!

int n , k ; 
string s;
int a[N] ; 

string tmp[N] ; 
int ts ; 

int solve(int l , int r){
        int ret = 0 ;   
        int x = r - l + 1; 
        for(int i = 0 ;i <= ts ; i ++){
              //  cout<< tmp[i] <<" " ;
                ret+= (tmp[i].substr(l , x) == string(x , '1') ) ;
        }
       // cout<<"-----\n" ;
        //if(ts)
      //  exit(0) ;
        return ret ; 
}

int bit[N] ; 

I add(int pos, int x){
        for(pos++ ;pos<N;pos+=pos&-pos)
                bit[pos]+=x ; 
}

int upto(int x){
        x++ ;
        int ret = 0 ; 
        for(;x;x-=x&-x)
                ret+=bit[x] ; 
        return ret ;  
}

int get(int l, int r){
        return upto(r) - upto(l - 1) ; 
}

int solve2(int l ,int r){
        int ret = 0 ;
        for(int i = 0 ;i <= ts ;i++){
               // memset(bit , 0 , sizeof bit) ;
                vector<int> cont(n+1 , 0) , cont2(n+1 , 0);
                vector<pair<int,int>>v ; 
                int cnt = 0 ; 
                if(l == r){
                        ret += 2 * (tmp[i][l] -'0') ; 
                        continue; 
                }
                for(int j = 0 ;j < n ;j ++){
                        if(tmp[i][j] == '1'){
                                if(cnt){       
 
                                } else{
                                        cont[j]++ ; 
                                }
                                cnt++ ;
                        }else{
                                if(cnt){
                                        v.push_back({ j - cnt ,  j -1 }) ;
                                        cont[j-1]-- ; 
                                        cont2[j-1] ++ ; 
                                }else{
 
                                }
 
                                cnt = 0 ; 
                        }
                }
                if(cnt){
                        v.push_back({n - cnt , n - 1 }) ;
                        cont[n-1] -- ;
                        cont2[n-1] ++ ;
                }

                for(int j = 0 ;j <= l ;j ++){
                        ret += cont[j] ; 
                }
                for(int j = r  ; j < n ;j ++)
                        ret -= cont[j] ;

                int aux = 0 , aux2 = 0; 
                for(int j = 0 ;j <= l ;j ++)
                        aux += cont[j] ;
                for(int j = r ;j < n ; j ++)
                        aux2 += cont[j] ; 
                aux = !!aux ; aux2 = !!aux2 ;
                if(aux && aux2){
                        if(tmp[i].substr(l , r - l + 1) != string (r - l + 1 , '1'))
                                ret -= 2; 
                }else{
                        ret -= aux + aux2 ; 
                }
          /*      int q = 0 ;
                //ret -= aux ;         
                for(auto u : v){
                        if(u.first > l && u.second < r)
                                continue ;
                        if(u.first > l && u.first < r)
                                ret -- ; 
                        if(u.second > l && u.second < r)
                                 ret -- , q ++ ;

                }
                assert(aux ==  q) ; */
        }

        return ret / 2;
}

int main(){
        ios_base::sync_with_stdio(0) ;
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ;

        cin >> n >> k ; 
        cin >> s ; 
        tmp[0] = s; 
        for(int i = 0 ;i < n;i ++)
                a[i] = s[i] - '0' ;

        for(int i = 0 ;i < k ;i ++){
                string t ;
                int l , r;
                cin >> t ; 

                if(t == "toggle"){
                        cin >> l ;
                        tmp[ts+1] = tmp[ts] ;ts++;
                        tmp[ts][l-1] = '1' - tmp[ts][l-1] + '0';
                        a[l] ^=1 ; 
                } else{
                        cin >> l >> r; 
                        l-- ; r-=2; 
                        cout<< solve2(l , r) <<"\n"; 
                        tmp[ts + 1] = tmp[ts]  ; ts ++ ;

                }
        }
        
        return 0 ; 
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3456 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 3 ms 3456 KB Output is correct
4 Correct 5 ms 3456 KB Output is correct
5 Correct 3 ms 3456 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Correct 6 ms 3456 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5088 ms 4904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4480 KB Output is correct
2 Correct 1012 ms 4728 KB Output is correct
3 Correct 1894 ms 4728 KB Output is correct
4 Correct 1889 ms 4808 KB Output is correct
5 Runtime error 10 ms 9108 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3056 ms 4596 KB Output is correct
2 Correct 3067 ms 4980 KB Output is correct
3 Correct 2114 ms 4728 KB Output is correct
4 Correct 127 ms 4600 KB Output is correct
5 Runtime error 10 ms 9048 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3456 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 3 ms 3456 KB Output is correct
4 Correct 5 ms 3456 KB Output is correct
5 Correct 3 ms 3456 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Correct 6 ms 3456 KB Output is correct
8 Execution timed out 5088 ms 4904 KB Time limit exceeded
9 Halted 0 ms 0 KB -