Submission #887575

#	Time	Username	Problem	Language	Result	Execution time	Memory
887575		bobbilyking	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	4296 ms	340004 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)

constexpr ll NN = 300010*3;
#define N NN

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/3];

const ll INFTIME = NN;

namespace d2d {
    using key_t = int;
    using T = pl;
    
    T id = {0, 0};
    T f(T a, T b) {return {a.K+b.K, a.V+b.V};}
    
    struct seg {
        vector<T> t;
        vector<key_t> rr;
        #define rein(x) (lower_bound(A(rr), x) - rr.begin() + rr.size())
        void modify(key_t pin, T value) {  // set value at position p
            int p = rein(pin);
            assert(p != 2 * rr.size() and rr[p - rr.size()] == pin);
            for (t[p] = f(t[p], value); p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
        }
    
        T query(key_t lin, key_t rin) { // fold f on interval [l, r)
            T resl=id, resr=id;
            for (int l = rein(lin), r = rein(rin); 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);
        }
        #undef rein
    } t[2*N];

// setup functions
    void build() { 
        F(i, 0, N*2) {
            auto &rr = t[i].rr;
            sort(A(rr));
            rr.erase(unique(A(rr)), rr.end());
            t[i].t.assign(2*rr.size(), id);
        }
    }

    void pre_modify(int p, key_t k) {
        for (p+=N, t[p].rr.push_back(k); p /= 2;) t[p].rr.push_back(k);
    }

// actual functions
    void modify(int p, key_t k, T v) { 
        for (p+=N, t[p].modify(k, v); p /= 2;) t[p].modify(k, v);
    }

    T query(int l, int r, key_t l2, key_t r2) { // queries f(..[l2, r2)..) for all segtrees [l, r)
        T res = id;
        for(l += N, r += N; l < r; l /= 2, r /= 2) {
            if(l & 1) res = f(t[l++].query(l2, r2), res);
            if(r & 1) res = f(res, t[--r].query(l2, r2));
        }
        return res;
    }
}

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 (const auto &[type, l, r, time, qidx]: queries) if (type == query::INSERT) d2d::pre_modify(l, r);
    d2d::build();

    for (const auto &[type, l, r, time, qidx]: queries) {
        #define sgn(x) (x > 0 ? 1:-1)

        if (type == query::INSERT) {

            d2d::modify(l, r, {(INFTIME - abs(time)) * sgn(time), sgn(time)});
        } else { 
            auto [contribution, number] = d2d::query(0, l+1, r, NN);
            contribution -= number * (INFTIME - time);
            ans[qidx] += contribution;
        }
    }

    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) {}
      |     ^~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from street_lamps.cpp:5:
street_lamps.cpp: In member function 'void d2d::seg::modify(d2d::key_t, d2d::T)':
street_lamps.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             assert(p != 2 * rr.size() and rr[p - rr.size()] == pin);
      |                    ~~^~~~~~~~~~~~~~~~

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