Submission #742337

#	Time	Username	Problem	Language	Result	Execution time	Memory
742337		becaido	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1183 ms	89196 KiB

street_lamps

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 3e5 + 5;

int n, q;
string str;
int ans[SIZE];
set<pair<int, int>> s;
array<int, 3> ask[SIZE];
vector<array<int, 4>> op;

void add(int u, int d, int l, int r, int x, int t) {
    op.pb(array<int, 4>{d, r, x, t});
    op.pb(array<int, 4>{d, l - 1, -x, t});
    op.pb(array<int, 4>{u - 1, r, -x, t});
    op.pb(array<int, 4>{u - 1, l - 1, x, t});
}
void add(int p, int x, int t) {
    int l = p, r = p;
    auto it = s.lower_bound({p + 1, 0});
    if (it != s.end() && it->F == p + 1) {
        r = it->S;
        s.erase(it);
    }
    it = s.lower_bound({p + 1, 0});
    if (it != s.begin() && prev(it)->S == p - 1) {
        it--;
        l = it->F;
        s.erase(it);
    }
    s.emplace(l, r);
    add(l, p, p, r, x, t);
}
void del(int p, int x, int t) {
    auto it = prev(s.lower_bound({p + 1, 0}));
    auto [l, r] = *it;
    s.erase(it);
    if (l < p) s.emplace(l, p - 1);
    if (p < r) s.emplace(p + 1, r);
    add(l, p, p, r, -x, t);
}

inline bool cmp(const array<int, 4>& lhs, const array<int, 4>& rhs) {
    return lhs[3] != rhs[3] ? lhs[3] < rhs[3] : lhs[0] != rhs[0] ? lhs[0] > rhs[0] : lhs[1] != rhs[1] ? lhs[1] > rhs[1] : lhs[2] != 0;
}
inline bool cmp2(const array<int, 4>& lhs, const array<int, 4>& rhs) {
    return lhs[0] != rhs[0] ? lhs[0] > rhs[0] : lhs[1] != rhs[1] ? lhs[1] > rhs[1] : lhs[2] != 0;
}

int bit[SIZE];
void upd(int pos, int x) {
    for (; pos; pos -= pos & -pos) bit[pos] += x;
}
int que(int pos) {
    int re = 0;
    for (; pos <= n; pos += pos & -pos) re += bit[pos];
    return re;
}

// opx >= quex, opy >= quey, opt <= quet
void divide(vector<array<int, 4>> &op) {
    if (op.size() <= 1) return;
    int mid = op.size() / 2;
    vector<array<int, 4>> opl, opr;
    FOR (i, 0, mid - 1) opl.pb(op[i]);
    FOR (i, mid, op.size() - 1) opr.pb(op[i]);
    op.clear();
    divide(opl);
    divide(opr);

    for (int il = 0, ir = 0; il < opl.size() || ir < opr.size();) {
        if (il < opl.size() && (ir == opr.size() || cmp2(opl[il], opr[ir]))) {
            if (opl[il][2] != 0) upd(opl[il][1], opl[il][2]);
            op.pb(opl[il++]);
        } else {
            if (opr[ir][2] == 0) ans[opr[ir][3]] += que(opr[ir][1]);
            op.pb(opr[ir++]);
        }
    }
    for (auto [x, y, v, t] : opl) if (v != 0) upd(y, -v);
    opl.clear(), opr.clear();
}

void solve() {
    cin >> n >> q;
    cin >> str, str = " " + str;
    for (int i = 1, l = 0; i <= n; i++) if (str[i] == '1') {
        if (l == 0) l = i;
        if (i == n || str[i + 1] != '1') {
            s.emplace(l, i);
            add(l, i, l, i, q, 1);
            l = 0;
        }
    }
    FOR (i, 1, q) {
        string t;
        cin >> t;
        ans[i] = -1;
        if (t[0] == 't') ask[i][0] = 1, cin >> ask[i][1];
        else ask[i][0] = 2, cin >> ask[i][1] >> ask[i][2], ask[i][2]--;
    }
    FOR (i, 1, q) {
        auto [t, x, y] = ask[i];
        if (t == 1) {
            if (i == q) continue;
            if (str[x] == '0') add(x, q - i, i);
            else del(x, q - i, i);
            str[x] = '1' - str[x] + '0';
        } else {
            ans[i] = 0;
            op.pb(array<int, 4>{x, y, 0, i});
            auto it = s.lower_bound({x + 1, 0});
            if (it == s.begin()) continue;
            it--;
            if (it->F <= x && y <= it->S) ans[i] -= q - i;
        }
    }
    sort(op.begin(), op.end(), [](auto lhs, auto rhs) {
        return cmp(lhs, rhs);
    });
    divide(op);
    FOR (i, 1, q) if (ans[i] != -1) cout << ans[i] << '\n';
}

int main() {
    Waimai;
    solve();
}

Compilation message (stderr)

street_lamps.cpp: In function 'void divide(std::vector<std::array<int, 4> >&)':
street_lamps.cpp:90:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for (int il = 0, ir = 0; il < opl.size() || ir < opr.size();) {
      |                              ~~~^~~~~~~~~~~~
street_lamps.cpp:90:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for (int il = 0, ir = 0; il < opl.size() || ir < opr.size();) {
      |                                                 ~~~^~~~~~~~~~~~
street_lamps.cpp:91:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if (il < opl.size() && (ir == opr.size() || cmp2(opl[il], opr[ir]))) {
      |             ~~~^~~~~~~~~~~~
street_lamps.cpp:91:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if (il < opl.size() && (ir == opr.size() || cmp2(opl[il], opr[ir]))) {
      |                                 ~~~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20