oj.uz

Submission #684832

# Submission time Handle Problem Language Result Execution time Memory
684832 2023-01-22T14:45:53 Z vovamr Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2072 ms 102180 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("-O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#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) {
        if (q1[x].empty() || q1[x].back() != y) {
			q1[x].emplace_back(y);
		}
    }
}
inline void prep1() {
    for (int i = 0; i < N; ++i) {
		f1[i].resize(sz(q1[i]) + 3);
		f2[i].resize(sz(q1[i]) + 3);
    }
}
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<ve<int>> al_segs(n);
    for (auto &[r, l] : mp) al_segs[r].pb(l);
 
    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[p - 1].pb(l);
                if (p < r) al_segs[r].pb(p + 1);
                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[R].pb(L);
                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 (int r = n - 1; ~r; --r) {
		for (const auto &l : al_segs[r]) {
			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 39 ms 40184 KB Output is correct
2 Correct 38 ms 40156 KB Output is correct
3 Correct 38 ms 40192 KB Output is correct
4 Correct 41 ms 40276 KB Output is correct
5 Correct 40 ms 40160 KB Output is correct
6 Correct 41 ms 40148 KB Output is correct
7 Correct 39 ms 40208 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 45560 KB Output is correct
2 Correct 512 ms 45620 KB Output is correct
3 Correct 732 ms 47580 KB Output is correct
4 Correct 1354 ms 91760 KB Output is correct
5 Correct 1334 ms 82776 KB Output is correct
6 Correct 1428 ms 93944 KB Output is correct
7 Correct 276 ms 52012 KB Output is correct
8 Correct 245 ms 53356 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 40396 KB Output is correct
2 Correct 50 ms 40428 KB Output is correct
3 Correct 44 ms 40364 KB Output is correct
4 Correct 42 ms 40192 KB Output is correct
5 Correct 2045 ms 95756 KB Output is correct
6 Correct 1696 ms 91456 KB Output is correct
7 Correct 1268 ms 81988 KB Output is correct
8 Correct 238 ms 53408 KB Output is correct
9 Correct 115 ms 43932 KB Output is correct
10 Correct 120 ms 44236 KB Output is correct
11 Correct 142 ms 44304 KB Output is correct
12 Correct 234 ms 51984 KB Output is correct
13 Correct 230 ms 53368 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 40312 KB Output is correct
2 Correct 41 ms 40416 KB Output is correct
3 Correct 40 ms 40392 KB Output is correct
4 Correct 42 ms 40456 KB Output is correct
5 Correct 514 ms 79236 KB Output is correct
6 Correct 941 ms 86852 KB Output is correct
7 Correct 1481 ms 93568 KB Output is correct
8 Correct 2072 ms 102180 KB Output is correct
9 Correct 649 ms 45616 KB Output is correct
10 Correct 630 ms 45520 KB Output is correct
11 Correct 637 ms 45632 KB Output is correct
12 Correct 639 ms 45448 KB Output is correct
13 Correct 656 ms 45632 KB Output is correct
14 Correct 617 ms 45556 KB Output is correct
15 Correct 270 ms 52028 KB Output is correct
16 Correct 236 ms 53356 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 40184 KB Output is correct
2 Correct 38 ms 40156 KB Output is correct
3 Correct 38 ms 40192 KB Output is correct
4 Correct 41 ms 40276 KB Output is correct
5 Correct 40 ms 40160 KB Output is correct
6 Correct 41 ms 40148 KB Output is correct
7 Correct 39 ms 40208 KB Output is correct
8 Correct 405 ms 45560 KB Output is correct
9 Correct 512 ms 45620 KB Output is correct
10 Correct 732 ms 47580 KB Output is correct
11 Correct 1354 ms 91760 KB Output is correct
12 Correct 1334 ms 82776 KB Output is correct
13 Correct 1428 ms 93944 KB Output is correct
14 Correct 276 ms 52012 KB Output is correct
15 Correct 245 ms 53356 KB Output is correct
16 Correct 54 ms 40396 KB Output is correct
17 Correct 50 ms 40428 KB Output is correct
18 Correct 44 ms 40364 KB Output is correct
19 Correct 42 ms 40192 KB Output is correct
20 Correct 2045 ms 95756 KB Output is correct
21 Correct 1696 ms 91456 KB Output is correct
22 Correct 1268 ms 81988 KB Output is correct
23 Correct 238 ms 53408 KB Output is correct
24 Correct 115 ms 43932 KB Output is correct
25 Correct 120 ms 44236 KB Output is correct
26 Correct 142 ms 44304 KB Output is correct
27 Correct 234 ms 51984 KB Output is correct
28 Correct 230 ms 53368 KB Output is correct
29 Correct 42 ms 40312 KB Output is correct
30 Correct 41 ms 40416 KB Output is correct
31 Correct 40 ms 40392 KB Output is correct
32 Correct 42 ms 40456 KB Output is correct
33 Correct 514 ms 79236 KB Output is correct
34 Correct 941 ms 86852 KB Output is correct
35 Correct 1481 ms 93568 KB Output is correct
36 Correct 2072 ms 102180 KB Output is correct
37 Correct 649 ms 45616 KB Output is correct
38 Correct 630 ms 45520 KB Output is correct
39 Correct 637 ms 45632 KB Output is correct
40 Correct 639 ms 45448 KB Output is correct
41 Correct 656 ms 45632 KB Output is correct
42 Correct 617 ms 45556 KB Output is correct
43 Correct 270 ms 52028 KB Output is correct
44 Correct 236 ms 53356 KB Output is correct
45 Correct 167 ms 43548 KB Output is correct
46 Correct 295 ms 43504 KB Output is correct
47 Correct 888 ms 63328 KB Output is correct
48 Correct 1292 ms 91444 KB Output is correct
49 Correct 119 ms 44432 KB Output is correct
50 Correct 119 ms 44324 KB Output is correct
51 Correct 127 ms 44440 KB Output is correct
52 Correct 123 ms 44332 KB Output is correct
53 Correct 124 ms 44492 KB Output is correct
54 Correct 126 ms 44364 KB Output is correct