Submission #887550

#	Time	Username	Problem	Language	Result	Execution time	Memory
887550		bobbilyking	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1262 ms	53244 KiB

street_lamps

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)

#define NN 300010
#define M 1000000007 // 998244353

struct query {
    enum {
        INSERT,
        QUERY
    } type;
    ll l, r; // [l, r]
    ll time;
    ll qidx;

    query(ll l, ll r, ll time): l(l), r(r), time(time), type(INSERT) {}
    query(ll l, ll r, ll time, ll qidx): l(l), r(r), time(time), qidx(qidx), type(QUERY) {}
};
ll ans[NN];

const ll INFTIME = NN;

namespace seg {
    typedef pl T;
    T id={0, 0};
    T f(T a, T b) {return {a.K + b.K, a.V + b.V};}

    T t[2 * NN];
    ll n=NN;  // array size

    vl record;

    void modify(ll p, T value) {  // set value at position p
        record.push_back(p);
        for (p+=n, t[p] = f(t[p], value); p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
    }

    void reset() {
        for (auto p: record) {
            for (p+=n, t[p] = id; p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
        }
        record.clear();
    }

    T query(ll l, ll r) { // fold f on interval [l, r)
      T resl=id, resr=id;
      for (l += n, r += n; l < r; l /= 2, r /= 2) {
        if (l&1) resl = f(resl, t[l++]);
        if (r&1) resr = f(t[--r], resr);
      }
      return f(resl, resr);
    }
}

void solve(vector<query>::iterator l, vector<query>::iterator r) {
    if (r-l <= 1) return;
    auto mid = l + (r-l)/2;
    solve(l, mid); solve(mid, r);
    auto cmp = [](const auto &a, const auto &b) {return a.l < b.l; };
    sort(l, mid, cmp); sort(mid, r, cmp);
    auto lit = l, rit = mid;

    // cdq on {number of points (A <= (l <= r) <= B), sum of weights of ponits }
    #define sgn(x) (x < 0 ? -1:1)
    while (rit != r) {
        if (lit != mid and lit->l <= rit->l) { // insert
            auto [type, l, r, time, _] = *lit++;
            if (type == query::INSERT) {
                seg::modify(r, {(INFTIME - abs(time)) * sgn(time), sgn(time)});
            }
        } else { 
            auto [type, l, r, time, qidx] = *rit++;
            if (type == query::QUERY) {
                auto [contribution, number] = seg::query(r, NN);
                contribution -= number * (INFTIME - time);
                ans[qidx] += contribution;
            }
        }
    }
    seg::reset();
}

int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    vector<query> queries; 
    
    G(n) G(q)
    GS(s) set<pl> intervals;
    // optimizzation: intstead of calling insert n times, just push back immidiately

    auto insert = [&](ll i, ll time) {
        pl to_add{i, i};
        auto it = intervals.lower_bound({i, i});
        if (it != intervals.end() and it->K == i+1) {
            to_add.V = it->V;
            queries.push_back(query(it->K, it->V, -time));
            intervals.erase(it);
        }
        it = intervals.lower_bound({i, i});
        if (it != intervals.begin() and (*--it).V == i-1) {
            to_add.K = it->K;
            queries.push_back(query(it->K, it->V, -time));
            intervals.erase(it);
        }
        intervals.insert(to_add);
        queries.push_back(query(to_add.K, to_add.V, time));
    };
    auto remove = [&](ll i, ll time) {
        auto [l, r] = *--intervals.upper_bound({i, NN});
        intervals.erase(--intervals.upper_bound({i, NN}));
        queries.push_back(query(l, r, -time));
        if (l <= i-1) {
            queries.push_back(query(l, i-1, time));
            intervals.insert({l, i-1});
        }
        if (i + 1 <= r) {
            queries.push_back(query(i+1, r, time));
            intervals.insert({i+1, r});
        }
    };

    {
        ll l = -1, r = -1;
        F(i, 0, n) {
            if (s[i] == '1') {
                if (l == -1) l = i; 
                r = i;
            } else {
                if (l != -1) {
                    intervals.insert({l, r}); 
                    queries.push_back(query(l, r, 1));
                }
                l = r = -1;
            }
        }
        if (l != -1) {
            intervals.insert({l, r}); 
            queries.push_back(query(l, r, 1));
        }
    }

    ll nq = 0; // qidx indexing
    F(time, 2, q+2) {
        GS(input)
        if (input == "toggle") {
            G(i)  --i;
            if (s[i] == '1') remove(i, time);
            else insert(i, time);
            s[i] ^=1;
        } else {
            G(a) G(b) 
            queries.push_back(query(a-1, b-2, time, nq++));
        }
    }

    // for (auto [type, l, r, time, qidx]: queries) {
    //     cout << (type == query::INSERT ? "INS":"QUE") << " " << l << " " << r << " " << time << " : " << (type == query::INSERT ? -1: qidx) << endl;
    // }

    solve(A(queries));

    F(i, 0, nq) cout << ans[i] << '\n';
}

Compilation message (stderr)

street_lamps.cpp: In constructor 'query::query(ll, ll, ll)':
street_lamps.cpp:33:8: warning: 'query::time' will be initialized after [-Wreorder]
   33 |     ll time;
      |        ^~~~
street_lamps.cpp:31:7: warning:   'query::<unnamed enum> query::type' [-Wreorder]
   31 |     } type;
      |       ^~~~
street_lamps.cpp:36:5: warning:   when initialized here [-Wreorder]
   36 |     query(ll l, ll r, ll time): l(l), r(r), time(time), type(INSERT) {}
      |     ^~~~~
street_lamps.cpp: In constructor 'query::query(ll, ll, ll, ll)':
street_lamps.cpp:34:8: warning: 'query::qidx' will be initialized after [-Wreorder]
   34 |     ll qidx;
      |        ^~~~
street_lamps.cpp:31:7: warning:   'query::<unnamed enum> query::type' [-Wreorder]
   31 |     } type;
      |       ^~~~
street_lamps.cpp:37:5: warning:   when initialized here [-Wreorder]
   37 |     query(ll l, ll r, ll time, ll qidx): l(l), r(r), time(time), qidx(qidx), type(QUERY) {}
      |     ^~~~~

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