oj.uz

Submission #790147

# Submission time Handle Problem Language Result Execution time Memory
790147 2023-07-22T11:07:37 Z GrindMachine Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1897 ms 220580 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 3e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

struct compressed_fenwick{
    gp_hash_table<int,int> tr;

    int lsb(int x) {
        return x & -x;
    }

    void pupd(int i, int v){
        for(; i < N; i += lsb(i)){
            tr[i] += v; 
        }
    }

    int sum(int i){
        int res = 0;
        for(; i; i -= lsb(i)){
            if(tr.find(i) != tr.end()){
                res += tr[i];
            }
        }
        return res;
    }

    int query(int l, int r){
        if(l > r) return 0;
        return sum(r) - sum(l-1);
    }
};

template<typename T>
struct fenwick {
    int siz;
    vector<compressed_fenwick> tree;

    fenwick(int n) {
        siz = n;
        tree = vector<compressed_fenwick>(n + 1);
    }

    int lsb(int x) {
        return x & -x;
    }

    void pupd(int i, int pos, T v) {
        while (i <= siz) {
            tree[i].pupd(pos,v);
            i += lsb(i);
        }
    }

    T sum(int i, int pos) {
        T res = 0;

        while (i) {
            res += tree[i].query(pos,N-1);
            i -= lsb(i);
        }

        return res;
    }

    T query(int l, int r, int pos) {
        if (l > r) return 0;
        T res = sum(r,pos) - sum(l-1,pos);
        return res;
    }
};

void solve(int test_case)
{
    int n,q; cin >> n >> q;
    vector<int> a(n+5);
    rep1(i,n){
        char ch; cin >> ch;
        a[i] = ch-'0';
    }

    set<array<int,3>> active;
    vector<array<int,3>> segs;

    {
        int l = -1;
        rep1(i,n){
            if(!a[i]){
                if(l != -1){
                    active.insert({l,i-1,0});
                }

                l = -1;
            }
            else{
                if(l == -1){
                    l = i;
                }
            }
        }

        if(l != -1){
            active.insert({l,n,0});
        }
    }

    auto get_seg = [&](int i){
        auto it = active.upper_bound({i+1,-1,-1});
        if(it == active.begin()) return active.end();
        else{
            it--;
            auto [l,r,t] = *it;
            if(l <= i and r >= i){
                return it;
            }
            else{
                return active.end();
            }
        }
    };

    fenwick<int> fenw(n+5);

    auto insert_seg = [&](set<array<int,3>>::iterator it, int id){
        auto [l,r,t] = *it;
        segs.pb({l,r,id-t});
        fenw.pupd(l,r,id-t);
    };

    rep1(id,q){
        string t; cin >> t;
        if(t == "toggle"){
            int i; cin >> i;
            a[i] ^= 1;

            if(!a[i]){
                // unset
                auto it = get_seg(i);
                assert(it != active.end());
                auto [l,r,t] = *it;
                insert_seg(it,id);
                active.erase(it);

                if(l <= i-1){
                    active.insert({l,i-1,id});
                }
                if(i+1 <= r){
                    active.insert({i+1,r,id});
                }
            }
            else{
                // set
                auto it1 = get_seg(i-1);
                auto it2 = get_seg(i+1);
                
                int l = -1, r = -1;

                if(it1 != active.end()){
                    auto curr = *it1;
                    l = curr[0];                    
                    insert_seg(it1,id);
                    active.erase(it1);
                }

                if(it2 != active.end()){
                    auto curr = *it2;
                    r = curr[1];
                    insert_seg(it2,id);
                    active.erase(it2);
                }

                if(l != -1 and r != -1){
                    active.insert({l,r,id});
                }
                else if(l != -1){
                    active.insert({l,i,id});
                }
                else if(r != -1){
                    active.insert({i,r,id});
                }
                else{
                    active.insert({i,i,id});
                }
            }
        }
        else{
            int l,r; cin >> l >> r;
            r--;
            
            auto it = get_seg(l);
            int ans = 0;

            {
                auto [lx,rx,t] = *it;
                if(lx <= l and rx >= r){
                    ans += id-t;
                }
            }

            ans += fenw.query(1,l,r);

            /*

            for(auto [lx,rx,wx] : segs){
                if(lx <= l and rx >= r){
                    ans += wx;
                }
            }
    
            */

            cout << ans << endl;
        }
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 4432 KB Output is correct
2 Correct 429 ms 4620 KB Output is correct
3 Correct 996 ms 9820 KB Output is correct
4 Correct 1681 ms 180280 KB Output is correct
5 Correct 1855 ms 195816 KB Output is correct
6 Correct 1554 ms 185756 KB Output is correct
7 Correct 410 ms 65460 KB Output is correct
8 Correct 483 ms 66844 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1554 ms 220580 KB Output is correct
6 Correct 1897 ms 214736 KB Output is correct
7 Correct 1811 ms 195612 KB Output is correct
8 Correct 432 ms 66848 KB Output is correct
9 Correct 174 ms 1228 KB Output is correct
10 Correct 213 ms 1152 KB Output is correct
11 Correct 192 ms 1340 KB Output is correct
12 Correct 432 ms 65464 KB Output is correct
13 Correct 426 ms 66868 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 1156 ms 76228 KB Output is correct
6 Correct 1687 ms 143108 KB Output is correct
7 Correct 1641 ms 185968 KB Output is correct
8 Correct 1488 ms 201980 KB Output is correct
9 Correct 373 ms 3924 KB Output is correct
10 Correct 305 ms 6676 KB Output is correct
11 Correct 401 ms 3860 KB Output is correct
12 Correct 342 ms 6708 KB Output is correct
13 Correct 371 ms 3944 KB Output is correct
14 Correct 314 ms 6596 KB Output is correct
15 Correct 406 ms 65484 KB Output is correct
16 Correct 429 ms 66880 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 341 ms 4432 KB Output is correct
9 Correct 429 ms 4620 KB Output is correct
10 Correct 996 ms 9820 KB Output is correct
11 Correct 1681 ms 180280 KB Output is correct
12 Correct 1855 ms 195816 KB Output is correct
13 Correct 1554 ms 185756 KB Output is correct
14 Correct 410 ms 65460 KB Output is correct
15 Correct 483 ms 66844 KB Output is correct
16 Correct 3 ms 980 KB Output is correct
17 Correct 3 ms 980 KB Output is correct
18 Correct 3 ms 852 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1554 ms 220580 KB Output is correct
21 Correct 1897 ms 214736 KB Output is correct
22 Correct 1811 ms 195612 KB Output is correct
23 Correct 432 ms 66848 KB Output is correct
24 Correct 174 ms 1228 KB Output is correct
25 Correct 213 ms 1152 KB Output is correct
26 Correct 192 ms 1340 KB Output is correct
27 Correct 432 ms 65464 KB Output is correct
28 Correct 426 ms 66868 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 2 ms 724 KB Output is correct
31 Correct 3 ms 852 KB Output is correct
32 Correct 2 ms 980 KB Output is correct
33 Correct 1156 ms 76228 KB Output is correct
34 Correct 1687 ms 143108 KB Output is correct
35 Correct 1641 ms 185968 KB Output is correct
36 Correct 1488 ms 201980 KB Output is correct
37 Correct 373 ms 3924 KB Output is correct
38 Correct 305 ms 6676 KB Output is correct
39 Correct 401 ms 3860 KB Output is correct
40 Correct 342 ms 6708 KB Output is correct
41 Correct 371 ms 3944 KB Output is correct
42 Correct 314 ms 6596 KB Output is correct
43 Correct 406 ms 65484 KB Output is correct
44 Correct 429 ms 66880 KB Output is correct
45 Correct 150 ms 2324 KB Output is correct
46 Correct 215 ms 2200 KB Output is correct
47 Correct 826 ms 67452 KB Output is correct
48 Correct 1696 ms 179880 KB Output is correct
49 Correct 202 ms 940 KB Output is correct
50 Correct 216 ms 1020 KB Output is correct
51 Correct 193 ms 900 KB Output is correct
52 Correct 148 ms 1004 KB Output is correct
53 Correct 124 ms 912 KB Output is correct
54 Correct 135 ms 980 KB Output is correct