Submission #1165780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165780		SmuggingSpun	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	4290 ms	331384 KiB

street_lamps

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
int n, q;
string s;
namespace sub1{
    void solve(){
        vector<string>state;
        for(int _ = 0; _ < q; _++){
            string _t;
            cin >> _t;
            state.emplace_back(s);
            if(_t == "toggle"){
                int i;
                cin >> i;
                s[i] = (s[i] == '0' ? '1' : '0');
            }
            else{
                int a, b, ans = state.size();
                cin >> a >> b;
                for(string& S : state){
                    for(int i = a; i < b; i++){
                        if(S[i] == '0'){
                            ans--;
                            break;
                        }
                    }
                }
                cout << ans << "\n";
            }
        }
    }
}
namespace sub2345{
    const int lim = 3e5 + 2;
    struct FenwickTree1D{
        int bit[lim];
        FenwickTree1D(){
            memset(bit, 0, sizeof(bit));
        }
        void update(int p, int x){
            for(; p < lim; p += p & -p){
                bit[p] += x;
            }
        }
        int get(int p){
            int ans = 0;
            for(; p > 0; p -= p & -p){
                ans += bit[p];
            }
            return ans;
        }
        int get(int l, int r){
            return get(r) - get(l - 1);
        }
    };
    struct FenwickTree2D{
        unordered_map<int, int>bit[lim];
        unordered_map<int, int>::iterator it;
        void update(int x, int y, int value){
            for(; x < lim; x += x & -x){
                for(int i = y; i < lim; i += i & -i){
                    bit[x][i] += value;
                }
            }
        }
        void update(int x, int y, int u, int v, int value){
            update(x, y, value);
            update(x, v + 1, -value);
            update(u + 1, y, -value);
            update(u + 1, v + 1, value);
        }
        int get(int x, int y){
            int ans = 0;
            for(; x > 0; x -= x & -x){
                for(int i = y; i > 0; i -= i & -i){
                    if((it = bit[x].find(i)) != bit[x].end()){
                        ans += it->second;
                    }
                }
            }
            return ans;
        }
    };
    FenwickTree1D bit_1d;
    FenwickTree2D bit_2d;
    pair<int, int>find_left_right(int i){
        int left = i, right = i, low = 1, high = i - 1;
        while(low <= high){
            int mid = (low + high) >> 1;
            if(bit_1d.get(mid, i - 1) == i - mid){
                high = (left = mid) - 1;
            }
            else{
                low = mid + 1;
            }
        }
        low = i + 1;
        high = n;
        while(low <= high){
            int mid = (low + high) >> 1;
            if(bit_1d.get(i + 1, mid) == mid - i){
                low = (right = mid) + 1;
            }
            else{
                high = mid - 1;
            }
        }
        return make_pair(left, right);
    }
    void update_0(int i, int N){
        s[i] = '0';
        bit_1d.update(i, -1);
        auto [left, right] = find_left_right(i);
        bit_2d.update(left, left, right, right, -N);
        if(left < i){
            bit_2d.update(left, left, i - 1, i - 1, N);
        }
        if(right > i){
            bit_2d.update(i + 1, i + 1, right, right, N);
        }
    }
    void update_1(int i, int N){
        s[i] = '1';
        bit_1d.update(i, 1);
        auto [left, right] = find_left_right(i);
        bit_2d.update(left, left, right, right, N);
        if(left < i){
            bit_2d.update(left, left, i - 1, i - 1, -N);
        }
        if(right > i){
            bit_2d.update(i + 1, i + 1, right, right, -N);
        }
    }
    void solve(){
        for(int i = 1; i <= n; i++){
            if(s[i] == '1'){
                int l = i++;
                while(i <= n && s[i] == '1'){
                    i++;
                }
                for(int j = l; j < i; j++){
                    bit_1d.update(j, 1);
                }
                bit_2d.update(l, l, i - 1, i - 1, q);
            }
        }
        for(int _q = 1; _q <= q; _q++){
            string _t;
            cin >> _t;
            if(_t == "toggle"){
                int i;
                cin >> i;
                if(s[i] == '1'){
                    update_0(i, q - _q);
                }
                else{
                    update_1(i, q - _q);
                }
            }
            else{
                int x, y;
                cin >> x >> y;
                cout << bit_2d.get(x, --y) - (bit_1d.get(x, y) == y - x + 1 ? q - _q : 0) << "\n";
            }
        }
    }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
    cin >> n >> q >> s;
    s = '#' + s;
    if(max(n, q) <= 100){
        sub1::solve();
    }
    else{
        sub2345::solve();
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:172:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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