답안 #790147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790147	2023-07-22T11:07:37 Z	GrindMachine	가로등 (APIO19_street_lamps)	C++17	100 / 100	1897 ms	220580 KB

street_lamps

// 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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