oj.uz

Submission #684751

# Submission time Handle Problem Language Result Execution time Memory
684751 2023-01-22T12:37:02 Z vovamr Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2390 ms 116572 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

int n;
const int N = 3e5 + 100;

ve<int> q1[N], f2[N];
ve<pii> f1[N];

inline void add_pt1(int x, int y) {
    for (x += 2; x < N; x += x & -x) {
        q1[x].pb(y);
    }
}
inline void prep1() {
    for (int i = 0; i < N; ++i) {
        sort(all(q1[i]));
        q1[i].erase(unique(all(q1[i])), q1[i].end());
        f1[i].resize(sz(q1[i]) + 6);
		f2[i].resize(sz(q1[i]) + 6);
    }
}
inline void upd1(int x, int y, const pii &c) {
    for (x += 2; x < N; x += x & -x) {
        int j = lower_bound(all(q1[x]), y) - q1[x].begin() + 2;
        for (; j < sz(f1[x]); j += j & -j) {
            f1[x][j].fi += c.fi;
            f1[x][j].se += c.se;
        }
    }
}
inline pii get1(int x, int y) {
    pii res = {0, 0};
    for (x += 2; x; x -= x & -x) {
        int j = upper_bound(all(q1[x]), y) - q1[x].begin() - 1 + 2;
        for (; j; j -= j & -j) {
            res.fi += f1[x][j].fi;
            res.se += f1[x][j].se;
        }
    }
    return res;
}

inline void upd2(int x, int y, const int &d) {
    for (x += 2; x < N; x += x & -x) {
        int j = lower_bound(all(q1[x]), y) - q1[x].begin() + 2;
        for (; j < sz(f2[x]); j += j & -j) f2[x][j] += d;
    }
}
inline int get2(int x, int y) {
    int ans = 0;
    for (x += 2; x; x -= x & -x) {
        int j = upper_bound(all(q1[x]), y) - q1[x].begin() - 1 + 2;
        for (; j; j -= j & -j) ans += f2[x][j];
    }
    return ans;
}

inline void add_dead_seg(int l, int r, int t1, int t2) {
//    cout << "del alive seg " << l + 1 << " " << r + 1 << " = "  << t1 << '\n';
//    cout << "add dead seg " << l + 1 << " " << r + 1 << " = [" << t1 << ", " << t2 << "]" << '\n';
    upd2(l, n - r - 1, t2 - t1 + 1);
    upd1(l, n - r - 1, mpp( -1, -t1) );
}
inline void add_inf_seg(int l, int r, int t) {
//    cout << "add alive seg " << l + 1 << " " << r + 1 << " = " << t << '\n';
    upd1(l, n - r - 1, mpp(1, t));
}

inline void solve() {
    int q;
    cin >> n >> q;
    ve<char> a(n), b;
    for (auto &i : a) cin >> i;
    b = a;

    map<int,int> mp;
    {
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] == '0') {
                if (cnt > 0) mp[i - 1] = i - 1 - cnt + 1;
                cnt = 0;
            }
            else ++cnt;
        }
        if (cnt > 0) mp[n - 1] = n - 1 - cnt + 1;
    }

    ve<pii> al_segs;
    for (auto &[r, l] : mp) al_segs.pb({l, r});

    ve<array<int,3>> op(q);
    for (int i = 0; i < q; ++i) {
        string s; cin >> s;
        if (s == "toggle") {
            int p;
            cin >> p, --p;
            op[i] = {0, p, p};

            if (a[p] == '1') {
                auto it = mp.lower_bound(p);
                auto [r, l] = *it;

                if (p > l) al_segs.pb({l, p - 1});
                if (p < r) al_segs.pb({p + 1, r});
                mp.erase(r);
                if (p > l) mp[p - 1] = l;
                if (p < r) mp[r] = p + 1;
            }
            else {
                int L = p, R = p;
                auto it = mp.lower_bound(p);

                if (it != mp.end()) {
                    auto [r, l] = *it;
                    if (p + 1 == l) {
                        R = r;
                    }
                }
                if (it != mp.begin()) {
                    --it;
                    auto [r, l] = *it;
                    if (p - 1 == r) {
                        L = l;
                    }
                }

                if (R != p) mp.erase(R);
                if (L != p) mp.erase(p - 1);

                al_segs.pb({L, R});
                mp[R] = L;
            }
            a[p] = (a[p] == '1' ? '0' : '1');
        }
        else {
            int l, r;
            cin >> l >> r, --l, --r;
            op[i] = {1, l, r - 1};
        }
    }

    for (auto &[l, r] : al_segs) {
        add_pt1(l, n - r - 1);
    }
    prep1();

    map<int,pii> f;

    {
        a = b;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] == '0') {
                if (cnt > 0) f[i - 1] = {i - 1 - cnt + 1, 0};
                cnt = 0;
            }
            else ++cnt;
        }
        if (cnt > 0) f[n - 1] = {n - 1 - cnt + 1, 0};
    }

    for (auto &[r, _] : f) {
        auto &[l, time] = _;
        add_inf_seg(l, r, 0);
    }

    int cur_time = 0;

    for (auto &[type, l, r] : op) {

        ++cur_time;

        if (type == 0) {

            int p = l;
            if (a[p] == '1') {
                auto it = f.lower_bound(p);
                auto [r, _] = *it; auto [l, time] = _;

                add_dead_seg(l, r, time, cur_time - 1);
                f.erase(r);

                if (p > l) f[p - 1] = {l, cur_time}, add_inf_seg(l, p - 1, cur_time);
                if (p < r) f[r] = {p + 1, cur_time}, add_inf_seg(p + 1, r, cur_time);
            }
            else {
                int L = p, R = p;
                auto it = f.lower_bound(p);

                if (it != f.end()) {
                    auto [r, _] = *it; auto [l, time] = _;
                    if (p + 1 == l) {
                        R = r;
                        add_dead_seg(l, r, time, cur_time - 1);
                    }
                }
                if (it != f.begin()) {
                    --it;
                    auto [r, _] = *it; auto [l, time] = _;
                    if (p - 1 == r) {
                        L = l;
                        add_dead_seg(l, r, time, cur_time - 1);
                    }
                }

                if (R != p) f.erase(R);
                if (L != p) f.erase(p - 1);

                add_inf_seg(L, R, cur_time);
                f[R] = {L, cur_time};
            }
            a[p] = (a[p] == '1' ? '0' : '1');
        }
        else {
            int sum_dead = get2( l, n - r - 1 );
            auto [cnt_alive, sum_time_alive] = get1(l, n - r - 1);

            int ans = sum_dead + cnt_alive * cur_time - sum_time_alive;

            cout << ans << '\n';
        }
    }
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 49572 KB Output is correct
2 Correct 46 ms 49532 KB Output is correct
3 Correct 49 ms 49644 KB Output is correct
4 Correct 46 ms 49620 KB Output is correct
5 Correct 48 ms 49548 KB Output is correct
6 Correct 47 ms 49620 KB Output is correct
7 Correct 45 ms 49568 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 70200 KB Output is correct
2 Correct 600 ms 70068 KB Output is correct
3 Correct 803 ms 69868 KB Output is correct
4 Correct 1437 ms 101828 KB Output is correct
5 Correct 1372 ms 93244 KB Output is correct
6 Correct 1573 ms 103936 KB Output is correct
7 Correct 291 ms 60348 KB Output is correct
8 Correct 272 ms 61700 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 49868 KB Output is correct
2 Correct 47 ms 49740 KB Output is correct
3 Correct 51 ms 49740 KB Output is correct
4 Correct 46 ms 49596 KB Output is correct
5 Correct 2390 ms 104692 KB Output is correct
6 Correct 1818 ms 100508 KB Output is correct
7 Correct 1358 ms 91728 KB Output is correct
8 Correct 274 ms 60932 KB Output is correct
9 Correct 119 ms 56168 KB Output is correct
10 Correct 130 ms 56716 KB Output is correct
11 Correct 123 ms 56908 KB Output is correct
12 Correct 264 ms 59612 KB Output is correct
13 Correct 263 ms 60876 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 49740 KB Output is correct
2 Correct 48 ms 49740 KB Output is correct
3 Correct 48 ms 49756 KB Output is correct
4 Correct 51 ms 49944 KB Output is correct
5 Correct 575 ms 86188 KB Output is correct
6 Correct 1032 ms 96860 KB Output is correct
7 Correct 1540 ms 103588 KB Output is correct
8 Correct 2352 ms 116572 KB Output is correct
9 Correct 756 ms 74264 KB Output is correct
10 Correct 798 ms 81760 KB Output is correct
11 Correct 748 ms 74196 KB Output is correct
12 Correct 766 ms 81700 KB Output is correct
13 Correct 758 ms 74308 KB Output is correct
14 Correct 784 ms 81640 KB Output is correct
15 Correct 276 ms 60300 KB Output is correct
16 Correct 307 ms 61664 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 49572 KB Output is correct
2 Correct 46 ms 49532 KB Output is correct
3 Correct 49 ms 49644 KB Output is correct
4 Correct 46 ms 49620 KB Output is correct
5 Correct 48 ms 49548 KB Output is correct
6 Correct 47 ms 49620 KB Output is correct
7 Correct 45 ms 49568 KB Output is correct
8 Correct 485 ms 70200 KB Output is correct
9 Correct 600 ms 70068 KB Output is correct
10 Correct 803 ms 69868 KB Output is correct
11 Correct 1437 ms 101828 KB Output is correct
12 Correct 1372 ms 93244 KB Output is correct
13 Correct 1573 ms 103936 KB Output is correct
14 Correct 291 ms 60348 KB Output is correct
15 Correct 272 ms 61700 KB Output is correct
16 Correct 49 ms 49868 KB Output is correct
17 Correct 47 ms 49740 KB Output is correct
18 Correct 51 ms 49740 KB Output is correct
19 Correct 46 ms 49596 KB Output is correct
20 Correct 2390 ms 104692 KB Output is correct
21 Correct 1818 ms 100508 KB Output is correct
22 Correct 1358 ms 91728 KB Output is correct
23 Correct 274 ms 60932 KB Output is correct
24 Correct 119 ms 56168 KB Output is correct
25 Correct 130 ms 56716 KB Output is correct
26 Correct 123 ms 56908 KB Output is correct
27 Correct 264 ms 59612 KB Output is correct
28 Correct 263 ms 60876 KB Output is correct
29 Correct 46 ms 49740 KB Output is correct
30 Correct 48 ms 49740 KB Output is correct
31 Correct 48 ms 49756 KB Output is correct
32 Correct 51 ms 49944 KB Output is correct
33 Correct 575 ms 86188 KB Output is correct
34 Correct 1032 ms 96860 KB Output is correct
35 Correct 1540 ms 103588 KB Output is correct
36 Correct 2352 ms 116572 KB Output is correct
37 Correct 756 ms 74264 KB Output is correct
38 Correct 798 ms 81760 KB Output is correct
39 Correct 748 ms 74196 KB Output is correct
40 Correct 766 ms 81700 KB Output is correct
41 Correct 758 ms 74308 KB Output is correct
42 Correct 784 ms 81640 KB Output is correct
43 Correct 276 ms 60300 KB Output is correct
44 Correct 307 ms 61664 KB Output is correct
45 Correct 235 ms 62900 KB Output is correct
46 Correct 346 ms 62124 KB Output is correct
47 Correct 858 ms 76396 KB Output is correct
48 Correct 1414 ms 101576 KB Output is correct
49 Correct 124 ms 57296 KB Output is correct
50 Correct 122 ms 57236 KB Output is correct
51 Correct 133 ms 57424 KB Output is correct
52 Correct 168 ms 57752 KB Output is correct
53 Correct 133 ms 57676 KB Output is correct
54 Correct 128 ms 57744 KB Output is correct