Submission #1099517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099517		Zero_OP	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	614 ms	35556 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i)
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i)
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true; return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true; return false;
}

using ll = long long;
using ld = long double;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); }
template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); }

const int MAX = 3e5 + 5;
const int inf = 1e9 + 9;

int n, q;
string s;
set<pair<int, int>> onSegments;
ll ans[MAX];

struct event{
    int t, type, l, r; //t is order of query
};

struct Fenwick{
    vector<int> bit_cnt;
    vector<ll> bit_sum;

    Fenwick(int n) : bit_cnt(n + 1, 0), bit_sum(n + 1, 0) {}

    void upd(int id, int cnt, int sum){
        for(; id > 0; id -= id & (-id)){
            bit_cnt[id] += cnt;
            bit_sum[id] += sum;
        }
    }

    pair<int, ll> qry(int id){
        int total_cnt = 0;
        ll total_sum = 0;
        for(; id < sz(bit_cnt); id += id & (-id)){
            total_cnt += bit_cnt[id];
            total_sum += bit_sum[id];
        }
        return {total_cnt, total_sum};
    }
};

void cdq(int l, int r, vector<event>& events, Fenwick& fenwick){
    if(l >= r) return;
    int mid = l + r >> 1;

    vector<int> upds, qrys;

    FOR(i, l, mid) if(events[i].type != 0) upds.push_back(i);
    FOR(i, mid + 1, r) if(events[i].type == 0) qrys.push_back(i);

//    cout << "conquer : " << l << ' ' << r << '\n';

    if(upds.empty() || qrys.empty());
    else{
        sort(all(upds), [&](int i, int j){ return events[i].l < events[j].l; });
        sort(all(qrys), [&](int i, int j){ return events[i].l < events[j].l; });

        vector<tuple<int, int, int>> saves;
        int j = 0;
        rep(i, 0, sz(qrys)){
            while(j < sz(upds) && events[upds[j]].l <= events[qrys[i]].l){
                fenwick.upd(events[upds[j]].r, events[upds[j]].type, events[upds[j]].t * events[upds[j]].type);
                saves.push_back({events[upds[j]].r, events[upds[j]].type, events[upds[j]].t * events[upds[j]].type});
//                cout << saves.back().first << ' ' << saves.back().second << '\n';
                ++j;
            }

            int num_cnt; ll num_sum;
            tie(num_cnt, num_sum) = fenwick.qry(events[qrys[i]].r);
            ans[events[qrys[i]].t] += 1LL * num_cnt * events[qrys[i]].t - num_sum;
//            cout << dbg(events[qrys[i]].t) << dbg(num_cnt) << ' ' << num_sum << '\n';
        }

         for(auto [pos, cnt, sum] : saves){
            fenwick.upd(pos, -cnt, -sum);
         }
    }

//    cout << "end layer\n\n";

    cdq(l, mid, events, fenwick);
    cdq(mid + 1, r, events, fenwick);
}

void testcase(){
    cin >> n >> q >> s;
    s = '?' + s;

    vector<event> events;
    FOR(i, 1, n){
        if(s[i] == '1'){
            int j = i;
            while(j < n && s[j + 1] == '1') ++j;

            onSegments.insert({i, j});
            events.push_back({0, +1, i, j});
            i = j;
        }
    }

    vector<int> queries;
    FOR(t, 1, q){
        string type;
        cin >> type;
        if(type == "toggle"){
            int i;
            cin >> i;

            if(s[i] == '1'){ //off
                auto it = onSegments.upper_bound({i, inf}); --it;
                int x, y;
                tie(x, y) = *it;

                onSegments.erase(it);
                events.push_back({t, -1, x, y});

                if(s[i - 1] == '1'){
                    onSegments.insert({x, i - 1});
                    events.push_back({t, +1, x, i - 1});
                }

                if(s[i + 1] == '1'){
                    onSegments.insert({i + 1, y});
                    events.push_back({t, +1, i + 1, y});
                }

                s[i] = '0';
            } else{ //on
                int x = i, y = i;

                if(s[i - 1] == '1'){
                    auto it = onSegments.upper_bound({i - 1, inf}); --it;
                    x = it -> first;
                    events.push_back({t, -1, x, i - 1});
                    onSegments.erase(it);
                }

                if(s[i + 1] == '1'){
                    auto it = onSegments.upper_bound({i + 1, inf}); --it;
                    y = it -> second;
                    events.push_back({t, -1, i + 1, y});
                    onSegments.erase(it);
                }

                events.push_back({t, +1, x, y});
                onSegments.insert({x, y});

                s[i] = '1';
            }
        } else{
            int l, r;
            cin >> l >> r;
            --r;

            events.push_back({t, 0, l, r});
            queries.push_back(t);
        }
    }

//    for(auto it : events){
//        cout << dbg(it.t) << dbg(it.l) << dbg(it.r) << dbg(it.type) << '\n';
//    }

    Fenwick fenwick(n);
    cdq(0, sz(events) - 1, events, fenwick);

    for(int i : queries){
        cout << ans[i] << '\n';
    }


}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define filename "task"
    if(fopen(filename".inp", "r")){
        freopen(filename".inp", "r", stdin);
        freopen(filename".out", "w", stdout);
    }

    int T = 1; //cin >> T;
    while(T--) testcase();

    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'bool minimize(T&, const T&)':
street_lamps.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |     if(a > b) return a = b, true; return false;
      |     ^~
street_lamps.cpp:15:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
street_lamps.cpp: In function 'bool maximize(T&, const T&)':
street_lamps.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |     if(a < b) return a = b, true; return false;
      |     ^~
street_lamps.cpp:20:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
street_lamps.cpp: In function 'void cdq(int, int, std::vector<event>&, Fenwick&)':
street_lamps.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |     int mid = l + r >> 1;
      |               ~~^~~
street_lamps.cpp:98:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |          for(auto [pos, cnt, sum] : saves){
      |                   ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:204:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         freopen(filename".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:205:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  205 |         freopen(filename".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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