oj.uz

Submission #1038081

# Submission time Handle Problem Language Result Execution time Memory
1038081 2024-07-29T12:50:16 Z vladilius Street Lamps (APIO19_street_lamps) C++17
40 / 100
 712 ms 244624 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
const int inf = numeric_limits<int> :: max();
 
struct FT{
    vector<int> bit;
    int n;
    void init(int ns){
        n = ns;
        bit.resize(n + 1);
    }
    int get(int v){
        int out = 0;
        while (v > 0){
            out += bit[v];
            v = (v & (v + 1)) - 1;
        }
        return out;
    }
    void upd(int v, int k){
        while (v <= n){
            bit[v] += k;
            v |= (v + 1);
        }
    }
    void updr(int l, int r, int k){
        if (l > r) return;
        upd(l, k);
        upd(r + 1, -k);
    }
};
 
struct ST{
    struct node{
        vector<int> x;
        int lg;
        FT T;
    };
    vector<node> t;
    vector<vector<int>> mp;
    int n, q;
    ST(int ns, int qs){
        n = ns; q = qs;
        t.resize(4 * n);
        for (int i = 1; i < t.size(); i++){
            t[i].x.pb(0);
        }
        mp.resize(q + 1);
        int lg = log2(n);
        for (int i = 1; i <= q; i++){
            mp[i].resize(lg + 1);
        }
        bld(1, 1, n, 0);
    }
    void bld(int v, int tl, int tr, int k){
        t[v].lg = k++;
        if (tl == tr) return;
        int tm = (tl + tr) / 2, vv = 2 * v;
        bld(vv, tl, tm, k);
        bld(vv + 1, tm + 1, tr, k);
    }
    vector<int> :: iterator it1, it2;
    void upd(int v, int tl, int tr, int& l, int& r, int& lr, int& rr, int& x){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            it1 = lower_bound(t[v].x.begin(), t[v].x.end(), lr);
            it2 = upper_bound(t[v].x.begin(), t[v].x.end(), rr);
            if (it1 == it2) return;
            it2--;
            int l1 = (int) (it1 - t[v].x.begin()), r1 = (int) (it2 - t[v].x.begin());
            t[v].T.updr(max(1, l1), r1, x);
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        upd(vv, tl, tm, l, r, lr, rr, x);
        upd(vv + 1, tm + 1, tr, l, r, lr, rr, x);
    }
    void upd(int l1, int r1, int l2, int r2, int x){
        upd(1, 1, n, l1, r1, l2, r2, x);
        // cout<<x<<" -> "<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<"\n";
    }
    int get(int v, int tl, int tr, int& l, int& i){
        int out = t[v].T.get(mp[i][t[v].lg]);
        if (tl == tr){
            return out;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (l <= tm){
            return out + get(vv, tl, tm, l, i);
        }
        return out + get(vv + 1, tm + 1, tr, l, i);
    }
    int get(int l, int i){
        return get(1, 1, n, l, i);
    }
    void add(int v, int tl, int tr, int& l, int& r, int& i){
        t[v].x.pb(r);
        mp[i][t[v].lg] = (int) t[v].x.size() - 1;
        if (tl == tr) return;
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (l <= tm){
            add(vv, tl, tm, l, r, i);
        }
        else {
            add(vv + 1, tm + 1, tr, l, r, i);
        }
    }
    void add(int l, int r, int i){
        add(1, 1, n, l, r, i);
    }
    void build(){
        for (int i = 1; i < t.size(); i++){
            t[i].T.init((int) t[i].x.size() - 1);
        }
    }
};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, q; cin>>n>>q;
    string s; cin>>s; s = '#' + s;
    vector<pii> qs = {{}};
    vector<int> rr;
    for (int qq = 1; qq <= q; qq++){
        string type; cin>>type;
        if (type == "toggle"){
            int k; cin>>k;
            qs.pb({k, 0});
        }
        else {
            int l, r; cin>>l>>r;
            qs.pb({l, --r});
            rr.pb(qq);
        }
    }
    
    auto cmp = [&](int i, int j){
        if (qs[i].ss == qs[j].ss){
            return qs[i].ff < qs[j].ff;
        }
        return qs[i].ss < qs[j].ss;
    };
    sort(rr.begin(), rr.end(), cmp);
    
    ST T(n, q);
    for (int i: rr){
        T.add(qs[i].ff, qs[i].ss, i);
    }
    T.build();
    
    set<pii> st;
    int i = 1;
    while (i <= n){
        if (s[i] == '0'){
            i++;
            continue;
        }
        int j = i;
        while (j <= n && s[j] == '1'){
            j++;
        }
        st.ins({i, j - 1});
        i = j;
    }
 
    for (int i = 1; i <= q; i++){
        auto& [a, b] = qs[i];
        if (!b){
            if (s[a] == '0'){
                st.ins({a, a});
                auto it = st.find({a, a});
                vector<pii> add;
                if (it != st.begin()){
                    auto it1 = prev(it);
                    auto [l, r] = *it1;
                    if (r == (a - 1)){
                        add.pb({l, r});
                    }
                }
                if (it != prev(st.end())){
                    auto it1 = next(it);
                    auto [l, r] = *it1;
                    if (l == (a + 1)){
                        add.pb({l, r});
                    }
                }
                if (add.size() == 2){
                    st.erase(it);
                    for (auto p: add) st.erase(p);
                    pii R = {add[0].ff, add[1].ss};
                    T.upd(R.ff, a, a, R.ss, -i);
                    st.ins(R);
                }
                else if (add.size() == 1){
                    st.erase(it);
                    for (auto p: add) st.erase(p);
                    pii R = ((add[0].ff > a) ? make_pair(a, add[0].ss) : make_pair(add[0].ff, a));
                    T.upd(R.ff, a, a, R.ss, -i);
                    st.ins(R);
                }
                else {
                    T.upd(a, a, a, a, -i);
                }
                s[a] = '1';
            }
            else {
                auto it = st.lower_bound({a + 1, -inf}); it--;
                auto [l, r] = *it;
                T.upd(l, a, a, r, i);
                st.erase(it);
                if (l < a) st.ins({l, a - 1});
                if (a < r) st.ins({a + 1, r});
                s[a] = '0';
            }
        }
        else {
            int out = T.get(qs[i].ff, i);
            if (!st.empty()){
                auto it = st.lower_bound({a + 1, -inf});
                if (it != st.begin()){
                    it--;
                    if ((*it).ff <= a && b <= (*it).ss){
                        out += i;
                    }
                }
            }
            cout<<out<<"\n";
        }
    }
}

Compilation message

street_lamps.cpp: In constructor 'ST::ST(int, int)':
street_lamps.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ST::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 1; i < t.size(); i++){
      |                         ~~^~~~~~~~~~
street_lamps.cpp: In member function 'void ST::build()':
street_lamps.cpp:118:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ST::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for (int i = 1; i < t.size(); i++){
      |                         ~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 40440 KB Output is correct
2 Correct 195 ms 42748 KB Output is correct
3 Correct 276 ms 55492 KB Output is correct
4 Correct 640 ms 220804 KB Output is correct
5 Correct 712 ms 223988 KB Output is correct
6 Correct 586 ms 213336 KB Output is correct
7 Correct 637 ms 242456 KB Output is correct
8 Correct 639 ms 244624 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1624 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1880 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 165 ms 40440 KB Output is correct
9 Correct 195 ms 42748 KB Output is correct
10 Correct 276 ms 55492 KB Output is correct
11 Correct 640 ms 220804 KB Output is correct
12 Correct 712 ms 223988 KB Output is correct
13 Correct 586 ms 213336 KB Output is correct
14 Correct 637 ms 242456 KB Output is correct
15 Correct 639 ms 244624 KB Output is correct
16 Runtime error 2 ms 1624 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -