oj.uz

Submission #790166

# Submission time Handle Problem Language Result Execution time Memory
790166 2023-07-22T11:29:13 Z GrindMachine Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1959 ms 220672 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
 
/*
 
#of moments when everybody in range was 1
 
1)
naive
 
2)
count #of times index has been 1
every time when turning off, add active time of ind
add extra active time if ind is active during query time
 
3)
every query is good on some suff
find the max time someone in the range is set
all queries after this is good
use segtree for range max queries
 
4)
can maintain a set of all active 1 segs
when toggle, upd set
also, store all segs (including non-active) and their active time in total
when query, find the sum of active times of all segs [lx,rx] s.t lx <= l <= r <= rx
sweepline + bit
 
5)
extend 4) idea?
answer queries online
find sum of active times of all segs [lx,rx] s.t lx <= l <= r <= rx
compressed bit at each node of seg
preprocess all compressed bits first, then make updates
alternatively, can also use sparse bit (with unordered_map/gp_hash_table)
also, add [l,r] contribution from the active set (guys from the active set are not in segs) 
 
*/
 
const int MOD = 1e9 + 7;
const int N = 3e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
 
struct sparse_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<sparse_fenwick> tree;
 
    fenwick(int n) {
        siz = n;
        tree = vector<sparse_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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 4468 KB Output is correct
2 Correct 474 ms 4728 KB Output is correct
3 Correct 1057 ms 9824 KB Output is correct
4 Correct 1640 ms 180224 KB Output is correct
5 Correct 1814 ms 195880 KB Output is correct
6 Correct 1614 ms 185864 KB Output is correct
7 Correct 463 ms 65492 KB Output is correct
8 Correct 433 ms 66880 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 1582 ms 220672 KB Output is correct
6 Correct 1959 ms 214564 KB Output is correct
7 Correct 1811 ms 195480 KB Output is correct
8 Correct 437 ms 66820 KB Output is correct
9 Correct 174 ms 1132 KB Output is correct
10 Correct 209 ms 1136 KB Output is correct
11 Correct 192 ms 1340 KB Output is correct
12 Correct 400 ms 65456 KB Output is correct
13 Correct 467 ms 66764 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 1212 ms 76448 KB Output is correct
6 Correct 1643 ms 143036 KB Output is correct
7 Correct 1629 ms 185600 KB Output is correct
8 Correct 1501 ms 201816 KB Output is correct
9 Correct 373 ms 3920 KB Output is correct
10 Correct 295 ms 6768 KB Output is correct
11 Correct 369 ms 3888 KB Output is correct
12 Correct 285 ms 6712 KB Output is correct
13 Correct 371 ms 3944 KB Output is correct
14 Correct 285 ms 6616 KB Output is correct
15 Correct 394 ms 65488 KB Output is correct
16 Correct 398 ms 66892 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 385 ms 4468 KB Output is correct
9 Correct 474 ms 4728 KB Output is correct
10 Correct 1057 ms 9824 KB Output is correct
11 Correct 1640 ms 180224 KB Output is correct
12 Correct 1814 ms 195880 KB Output is correct
13 Correct 1614 ms 185864 KB Output is correct
14 Correct 463 ms 65492 KB Output is correct
15 Correct 433 ms 66880 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 1582 ms 220672 KB Output is correct
21 Correct 1959 ms 214564 KB Output is correct
22 Correct 1811 ms 195480 KB Output is correct
23 Correct 437 ms 66820 KB Output is correct
24 Correct 174 ms 1132 KB Output is correct
25 Correct 209 ms 1136 KB Output is correct
26 Correct 192 ms 1340 KB Output is correct
27 Correct 400 ms 65456 KB Output is correct
28 Correct 467 ms 66764 KB Output is correct
29 Correct 3 ms 468 KB Output is correct
30 Correct 2 ms 724 KB Output is correct
31 Correct 2 ms 852 KB Output is correct
32 Correct 2 ms 980 KB Output is correct
33 Correct 1212 ms 76448 KB Output is correct
34 Correct 1643 ms 143036 KB Output is correct
35 Correct 1629 ms 185600 KB Output is correct
36 Correct 1501 ms 201816 KB Output is correct
37 Correct 373 ms 3920 KB Output is correct
38 Correct 295 ms 6768 KB Output is correct
39 Correct 369 ms 3888 KB Output is correct
40 Correct 285 ms 6712 KB Output is correct
41 Correct 371 ms 3944 KB Output is correct
42 Correct 285 ms 6616 KB Output is correct
43 Correct 394 ms 65488 KB Output is correct
44 Correct 398 ms 66892 KB Output is correct
45 Correct 174 ms 2288 KB Output is correct
46 Correct 216 ms 2188 KB Output is correct
47 Correct 870 ms 67476 KB Output is correct
48 Correct 1716 ms 179916 KB Output is correct
49 Correct 203 ms 912 KB Output is correct
50 Correct 219 ms 940 KB Output is correct
51 Correct 194 ms 1016 KB Output is correct
52 Correct 150 ms 928 KB Output is correct
53 Correct 137 ms 928 KB Output is correct
54 Correct 137 ms 1024 KB Output is correct