Submission #1078346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078346		Tymond	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1020 ms	245372 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct Node{
    ll s;
    int nxt[2];
    Node(){
        s = 0LL;
        nxt[0] = nxt[1] = -1;
    }
};

const int MAXN = 3e5 + 7;
const int BASE = (1 << 19);
int vec[MAXN];
vector<Node> tree[2 * BASE + 7];
int n, q;
string napis;
map<pii, int> date;

ll query(int ind, int l, int p, int k, int des){
    //cout << ind << ' ' << l << ' ' << p << '\n';
    if(l == p){
       // cout << tree[k][ind].s << '\n';
        return tree[k][ind].s;
    }

    int mid = (l + p) / 2;
    ll ret = tree[k][ind].s;
    if(des <= mid){
        if(tree[k][ind].nxt[0] != -1){
            ret += query(tree[k][ind].nxt[0], l, mid, k, des);
        }
    }else{
        if(tree[k][ind].nxt[1] != -1){
            ret += query(tree[k][ind].nxt[1], mid + 1, p, k, des);
        }
    }
    return ret;
}

ll getRes(int x, int y){
    //cout << "----------\nZAPYTANIE\n";
    //cout << x << ' ' << y << '\n';
    x += BASE;
    ll res = 0;
    while(x > 0){
        if(sz(tree[x])){
            //cout << "----\n";
            //cout << x << '\n';
            res += query(0, 0, BASE - 1, x, y);
        }
        x /= 2;
    }
    return res;
}

void updY(int ind, int l, int p, int a, int b, int val, int k){
    if(p < a || b < l){
        return;
    }
    if(a <= l && p <= b){
        //cout << "DODAJE: " << k << ' ' << ind << ' ' << val << '\n';
        tree[k][ind].s += val;
        return;
    }

    int mid = (l + p) / 2;
    if(a <= mid){
        if(tree[k][ind].nxt[0] == -1){
            tree[k].pb(Node());
            tree[k][ind].nxt[0] = sz(tree[k]) - 1;
        }
        updY(tree[k][ind].nxt[0], l, mid, a, b, val, k);
    }
    if(b >= mid + 1){
        if(tree[k][ind].nxt[1] == -1){
            tree[k].pb(Node());
            tree[k][ind].nxt[1] = sz(tree[k]) - 1;
        }
        updY(tree[k][ind].nxt[1], mid + 1, p, a, b, val, k);
    }
}

void updX(int v, int l, int p, int a, int b, int val){
    if(p < a || b < l){
        return;
    }

    if(a <= l && p <= b){
        //zrób dla drugiego wymiaru
        if(sz(tree[v]) == 0){
            tree[v].pb(Node());
        }

        updY(0, 0, BASE - 1, a, b, val, v);
        return;
    }

    int mid = (l + p) / 2;
    updX(2 * v, l, mid ,a, b, val);
    updX(2 * v + 1, mid + 1, p, a, b, val);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> q;
    cin >> napis;

    for(int i = 0; i < n; i++){
        vec[i + 1] = napis[i] - '0';
    }

    set<pii> s;
    int i = 1;
    for(i = 1; i <= n; i++){
        if(vec[i] == 0){
            continue;
        }

        int pocz = i;
        while(i + 1 <= n && vec[i + 1] == 1){
            i++;
        }

        s.insert({pocz, i});
        date[{pocz, i}] = 0;
    }

    for(i = 1; i <= q; i++){
        string t;
        cin >> t;
      //  cerr << "NIGGA\n";
        if(t == "query"){
            int x, y;
            cin >> x >> y;
            y--;
            
            int ans = 0;
            if(vec[x]){
                auto it = s.upper_bound({x, 1e9});
                it--;
                //cout << (*it).fi << ' ' << (*it).se << '\n';
                if((*it).se >= y && (*it).fi <= x){
                    ans += (i - date[*it]);
                }
            }
            //cout << ans << '\n';
            ans += getRes(x, y);
            cout << ans << '\n';
        }else{
            int ind;
            cin >> ind;

            if(vec[ind] == 1){
                auto it = s.upper_bound({ind, 1e9});
                it--;
              //  cout << (*it).fi << ' ' << (*it).se << ' ' << i - date[*it] << '\n';
                updX(1, 0, BASE - 1, (*it).fi, (*it).se, i - date[*it]);
                pii akt = *it;
                s.erase(it);
                if(ind > akt.fi){
                    s.insert({akt.fi, ind - 1});
                    date[{akt.fi, ind - 1}] = i;
                }

                if(ind < akt.se){
                    s.insert({ind + 1, akt.se});
                    date[{ind + 1, akt.se}] = i;
                }
            }else{
                auto it = s.upper_bound({ind, 1e9});
                if(!vec[ind - 1] && !vec[ind + 1]){
                    s.insert({ind, ind});
                    date[{ind, ind}] = i;
                }else if(!vec[ind - 1]){
                    updX(1, 0, BASE - 1, (*it).fi, (*it).se, i - date[*it]);
                    pii akt = *it;
                    s.erase(it);
                    s.insert({ind, akt.se});
                    date[{ind, akt.se}] = i;
                }else if(!vec[ind + 1]){
                    it--;
                    updX(1, 0, BASE - 1, (*it).fi, (*it).se, i - date[*it]);
                    pii akt = *it;
                    s.erase(it);
                    s.insert({akt.fi, ind});
                    date[{akt.fi, ind}] = i;
                }else{
                    //cerr << "NIGGER\n";
                    //cerr << (*it).fi << ' ' << (*it).se << '\n';
                    updX(1, 0, BASE - 1, (*it).fi, (*it).se, i - date[*it]);
                    pii usu = *it;

                    it--;
                    updX(1, 0, BASE - 1, (*it).fi, (*it).se, i - date[*it]);
                    pii usu2 = *it;

                    s.erase(usu);
                    s.erase(usu2);
                    s.insert({usu2.fi, usu.se});
                    date[{usu2.fi, usu.se}] = i;
                  //  cout << usu2.fi << ' ' << usu.se << '\n';
                }
            }
            vec[ind] = 1 - vec[ind];
        }
    }

    return 0;
}

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