oj.uz

Submission #684831

# Submission time Handle Problem Language Result Execution time Memory
684831 2023-01-22T14:44:46 Z vovamr Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2083 ms 102140 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) {
        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) if (sz(q1[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) if (sz(q1[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 40 ms 40148 KB Output is correct
2 Correct 39 ms 40152 KB Output is correct
3 Correct 39 ms 40140 KB Output is correct
4 Correct 44 ms 40160 KB Output is correct
5 Correct 41 ms 40248 KB Output is correct
6 Correct 48 ms 40176 KB Output is correct
7 Correct 40 ms 40148 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 45532 KB Output is correct
2 Correct 484 ms 45648 KB Output is correct
3 Correct 727 ms 47564 KB Output is correct
4 Correct 1311 ms 91888 KB Output is correct
5 Correct 1239 ms 82820 KB Output is correct
6 Correct 1406 ms 94064 KB Output is correct
7 Correct 152 ms 51944 KB Output is correct
8 Correct 165 ms 53356 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 40396 KB Output is correct
2 Correct 44 ms 40328 KB Output is correct
3 Correct 42 ms 40344 KB Output is correct
4 Correct 40 ms 40200 KB Output is correct
5 Correct 2005 ms 95740 KB Output is correct
6 Correct 1694 ms 91348 KB Output is correct
7 Correct 1265 ms 82052 KB Output is correct
8 Correct 167 ms 53384 KB Output is correct
9 Correct 109 ms 43972 KB Output is correct
10 Correct 123 ms 44208 KB Output is correct
11 Correct 113 ms 44292 KB Output is correct
12 Correct 159 ms 51980 KB Output is correct
13 Correct 171 ms 53308 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 40400 KB Output is correct
2 Correct 45 ms 40556 KB Output is correct
3 Correct 41 ms 40412 KB Output is correct
4 Correct 46 ms 40508 KB Output is correct
5 Correct 553 ms 79108 KB Output is correct
6 Correct 933 ms 86980 KB Output is correct
7 Correct 1449 ms 93680 KB Output is correct
8 Correct 2083 ms 102140 KB Output is correct
9 Correct 638 ms 45644 KB Output is correct
10 Correct 565 ms 45452 KB Output is correct
11 Correct 589 ms 45628 KB Output is correct
12 Correct 577 ms 45388 KB Output is correct
13 Correct 620 ms 45704 KB Output is correct
14 Correct 560 ms 45452 KB Output is correct
15 Correct 147 ms 51916 KB Output is correct
16 Correct 163 ms 53332 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 40148 KB Output is correct
2 Correct 39 ms 40152 KB Output is correct
3 Correct 39 ms 40140 KB Output is correct
4 Correct 44 ms 40160 KB Output is correct
5 Correct 41 ms 40248 KB Output is correct
6 Correct 48 ms 40176 KB Output is correct
7 Correct 40 ms 40148 KB Output is correct
8 Correct 376 ms 45532 KB Output is correct
9 Correct 484 ms 45648 KB Output is correct
10 Correct 727 ms 47564 KB Output is correct
11 Correct 1311 ms 91888 KB Output is correct
12 Correct 1239 ms 82820 KB Output is correct
13 Correct 1406 ms 94064 KB Output is correct
14 Correct 152 ms 51944 KB Output is correct
15 Correct 165 ms 53356 KB Output is correct
16 Correct 45 ms 40396 KB Output is correct
17 Correct 44 ms 40328 KB Output is correct
18 Correct 42 ms 40344 KB Output is correct
19 Correct 40 ms 40200 KB Output is correct
20 Correct 2005 ms 95740 KB Output is correct
21 Correct 1694 ms 91348 KB Output is correct
22 Correct 1265 ms 82052 KB Output is correct
23 Correct 167 ms 53384 KB Output is correct
24 Correct 109 ms 43972 KB Output is correct
25 Correct 123 ms 44208 KB Output is correct
26 Correct 113 ms 44292 KB Output is correct
27 Correct 159 ms 51980 KB Output is correct
28 Correct 171 ms 53308 KB Output is correct
29 Correct 47 ms 40400 KB Output is correct
30 Correct 45 ms 40556 KB Output is correct
31 Correct 41 ms 40412 KB Output is correct
32 Correct 46 ms 40508 KB Output is correct
33 Correct 553 ms 79108 KB Output is correct
34 Correct 933 ms 86980 KB Output is correct
35 Correct 1449 ms 93680 KB Output is correct
36 Correct 2083 ms 102140 KB Output is correct
37 Correct 638 ms 45644 KB Output is correct
38 Correct 565 ms 45452 KB Output is correct
39 Correct 589 ms 45628 KB Output is correct
40 Correct 577 ms 45388 KB Output is correct
41 Correct 620 ms 45704 KB Output is correct
42 Correct 560 ms 45452 KB Output is correct
43 Correct 147 ms 51916 KB Output is correct
44 Correct 163 ms 53332 KB Output is correct
45 Correct 163 ms 43692 KB Output is correct
46 Correct 290 ms 43452 KB Output is correct
47 Correct 826 ms 63352 KB Output is correct
48 Correct 1328 ms 91392 KB Output is correct
49 Correct 119 ms 44312 KB Output is correct
50 Correct 121 ms 44364 KB Output is correct
51 Correct 125 ms 44404 KB Output is correct
52 Correct 133 ms 44348 KB Output is correct
53 Correct 134 ms 44328 KB Output is correct
54 Correct 121 ms 44344 KB Output is correct