Submission #684829

#	Time	Username	Problem	Language	Result	Execution time	Memory
684829		vovamr	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2064 ms	102404 KiB

street_lamps

#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) {
        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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20