Submission #498407

#	Time	Username	Problem	Language	Result	Execution time	Memory
498407		ryangohca	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1181 ms	75316 KiB

street_lamps

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ti3 tuple<int, int, int>
#define ti4 tuple<int, int, int, int>
#define int long long
// Honestly, I love you, to the mysterious (SinB) place   ~ SinB, Sunny Summer
using namespace std;
const int N = 300005;
int fw[N+1];
void update(int x, int v) {
    for (; x<=N; x+=x&(-x)) fw[x] += v; 
}
int sum(int x) {
    int res = 0;
    for(; x; x-=x&(-x)) res += fw[x];
    return res;
}
set<pii> ranges;
vector<ti4> queries; // l,r,v/idx,isquery
int ans[300005];
void dnc(int s, int e){
    if (s >= e) return;
    int m = (s+e)/2;
    vector<ti3> upds;
    vector<ti3> qry;
    for (int i = s; i <= m; i++){
        auto [a, b, v, t] = queries[i];
        if (t == 0){
            upds.push_back({a, a, v});
            upds.push_back({b+1, a, -v});
        }
    }
    for (int i = m+1; i <= e; i++){
        auto [a, b, v, t] = queries[i];
        if (t == 1){
            qry.push_back({b, a, v});
        }
    }
    if (upds.empty() || qry.empty()){
        if (upds.empty() && !qry.empty()){
            // left side all queries, no use go there
            dnc(m+1, e);
        }
        if (qry.empty() && !upds.empty()){
            // right side all updates, no use go there
            dnc(s, m);
        }
        return;
    } else {
        sort(qry.begin(), qry.end());
        sort(upds.begin(), upds.end());
        int uidx = 0;
        for (auto [e, s, idx] : qry){
            while (uidx != upds.size() && get<0>(upds[uidx]) <= e){
                update(get<1>(upds[uidx]), get<2>(upds[uidx]));
                uidx++;
            }
            ans[idx] += sum(s);
        }
        // revert changes
        for (int i = uidx - 1; i >= 0; i--){
            update(get<1>(upds[i]), -get<2>(upds[i]));
        }
        dnc(s, m); dnc(m+1, e);
    }
}
main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    memset(ans, -1, sizeof ans);
    int n, q; cin >> n >> q;
    string s; cin >> s; s += '0';
    int lst = -1;
    for (int i = 1; i <= n+1; i++){
        if (s[i-1] == '1'){
            if (lst == -1) lst = i;
        } else {
            if (lst == -1) continue;
            ranges.insert({lst, i-1});
            // queries.push_back({lst, i-1, -0, 0}); // no effect
            lst = -1;
        }
    }
    for (int t = 1; t <= q; t++){
        string evt; cin >> evt;
        if (evt[0] == 'q'){
            ans[t] = 0;
            int a, b; cin >> a >> b; b--;
            // check if {a, b} is in some range alr
            auto itr = ranges.lower_bound({a, INT_MAX});
            if (itr != ranges.begin()){
                itr--;
                // itr->first <= a
                if (itr->second >= b){
                    ans[t] += t;
                }
            }
            queries.push_back({a, b, t, 1});
        } else {
            int x; cin >> x;
            if (s[x-1] == '0'){
                auto itr = ranges.lower_bound({x, 0});
                int ns = x, ne = x;
                if (itr != ranges.begin()){
                    auto prv = prev(itr);
                    if (prv->second == x - 1){
                        ns = prv->first;
                        queries.push_back({ns, prv->second, t, 0});
                        ranges.erase(prv);
                    }
                }
                if (itr != ranges.end()){
                    if (itr->first == x + 1){
                        ne = itr->second;
                        queries.push_back({itr->first, ne, t, 0});
                        ranges.erase(itr);
                    }
                }
                queries.push_back({ns, ne, -t, 0});
                ranges.insert({ns, ne});
            } else {
                auto itr = ranges.lower_bound({x, INT_MAX});
                itr--;
                if ((x-1) - itr->first >= 0){
                    queries.push_back({itr->first, x-1, -t, 0});
                    ranges.insert({itr->first, x-1});
                }
                if (itr->second - (x + 1) >= 0){
                    queries.push_back({x+1, itr->second, -t, 0});
                    ranges.insert({x+1, itr->second});
                }
                queries.push_back({itr->first, itr->second, t, 0});
                ranges.erase(itr);
            }
            s[x-1] = (s[x-1] == '0'? '1': '0');
        }
    }
    //for (auto [a, b, c, d]: queries) cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
    dnc(0, queries.size()-1);
    for (int i = 1; i <= q; i++){
        if (ans[i] != -1) cout << ans[i] << '\n'; 
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'void dnc(long long int, long long int)':
street_lamps.cpp:54:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             while (uidx != upds.size() && get<0>(upds[uidx]) <= e){
      |                    ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp: At global scope:
street_lamps.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main(){
      | ^~~~

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