oj.uz

Submission #887575

# Submission time Handle Problem Language Result Execution time Memory
887575 2023-12-14T18:40:57 Z bobbilyking Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4296 ms 340004 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 86628 KB Output is correct
2 Correct 29 ms 86620 KB Output is correct
3 Correct 31 ms 86620 KB Output is correct
4 Correct 31 ms 86856 KB Output is correct
5 Correct 30 ms 86708 KB Output is correct
6 Correct 31 ms 86716 KB Output is correct
7 Correct 30 ms 86620 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 141380 KB Output is correct
2 Correct 608 ms 140664 KB Output is correct
3 Correct 880 ms 143524 KB Output is correct
4 Correct 2634 ms 267132 KB Output is correct
5 Correct 2244 ms 242640 KB Output is correct
6 Correct 2733 ms 277500 KB Output is correct
7 Correct 204 ms 114984 KB Output is correct
8 Correct 170 ms 115024 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 87476 KB Output is correct
2 Correct 34 ms 87376 KB Output is correct
3 Correct 34 ms 87128 KB Output is correct
4 Correct 32 ms 86904 KB Output is correct
5 Correct 4008 ms 305240 KB Output is correct
6 Correct 3169 ms 288832 KB Output is correct
7 Correct 2153 ms 242284 KB Output is correct
8 Correct 167 ms 115312 KB Output is correct
9 Correct 101 ms 99960 KB Output is correct
10 Correct 112 ms 111372 KB Output is correct
11 Correct 111 ms 110848 KB Output is correct
12 Correct 192 ms 114972 KB Output is correct
13 Correct 192 ms 114700 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 87108 KB Output is correct
2 Correct 33 ms 87280 KB Output is correct
3 Correct 38 ms 87376 KB Output is correct
4 Correct 34 ms 87624 KB Output is correct
5 Correct 609 ms 184644 KB Output is correct
6 Correct 1656 ms 231920 KB Output is correct
7 Correct 2949 ms 279140 KB Output is correct
8 Correct 4296 ms 340004 KB Output is correct
9 Correct 796 ms 155676 KB Output is correct
10 Correct 788 ms 182364 KB Output is correct
11 Correct 831 ms 155564 KB Output is correct
12 Correct 819 ms 183308 KB Output is correct
13 Correct 849 ms 155304 KB Output is correct
14 Correct 782 ms 179604 KB Output is correct
15 Correct 162 ms 115208 KB Output is correct
16 Correct 183 ms 113848 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 86628 KB Output is correct
2 Correct 29 ms 86620 KB Output is correct
3 Correct 31 ms 86620 KB Output is correct
4 Correct 31 ms 86856 KB Output is correct
5 Correct 30 ms 86708 KB Output is correct
6 Correct 31 ms 86716 KB Output is correct
7 Correct 30 ms 86620 KB Output is correct
8 Correct 476 ms 141380 KB Output is correct
9 Correct 608 ms 140664 KB Output is correct
10 Correct 880 ms 143524 KB Output is correct
11 Correct 2634 ms 267132 KB Output is correct
12 Correct 2244 ms 242640 KB Output is correct
13 Correct 2733 ms 277500 KB Output is correct
14 Correct 204 ms 114984 KB Output is correct
15 Correct 170 ms 115024 KB Output is correct
16 Correct 34 ms 87476 KB Output is correct
17 Correct 34 ms 87376 KB Output is correct
18 Correct 34 ms 87128 KB Output is correct
19 Correct 32 ms 86904 KB Output is correct
20 Correct 4008 ms 305240 KB Output is correct
21 Correct 3169 ms 288832 KB Output is correct
22 Correct 2153 ms 242284 KB Output is correct
23 Correct 167 ms 115312 KB Output is correct
24 Correct 101 ms 99960 KB Output is correct
25 Correct 112 ms 111372 KB Output is correct
26 Correct 111 ms 110848 KB Output is correct
27 Correct 192 ms 114972 KB Output is correct
28 Correct 192 ms 114700 KB Output is correct
29 Correct 32 ms 87108 KB Output is correct
30 Correct 33 ms 87280 KB Output is correct
31 Correct 38 ms 87376 KB Output is correct
32 Correct 34 ms 87624 KB Output is correct
33 Correct 609 ms 184644 KB Output is correct
34 Correct 1656 ms 231920 KB Output is correct
35 Correct 2949 ms 279140 KB Output is correct
36 Correct 4296 ms 340004 KB Output is correct
37 Correct 796 ms 155676 KB Output is correct
38 Correct 788 ms 182364 KB Output is correct
39 Correct 831 ms 155564 KB Output is correct
40 Correct 819 ms 183308 KB Output is correct
41 Correct 849 ms 155304 KB Output is correct
42 Correct 782 ms 179604 KB Output is correct
43 Correct 162 ms 115208 KB Output is correct
44 Correct 183 ms 113848 KB Output is correct
45 Correct 220 ms 121728 KB Output is correct
46 Correct 327 ms 121596 KB Output is correct
47 Correct 1301 ms 175028 KB Output is correct
48 Correct 2523 ms 265780 KB Output is correct
49 Correct 128 ms 110500 KB Output is correct
50 Correct 112 ms 112156 KB Output is correct
51 Correct 114 ms 110900 KB Output is correct
52 Correct 118 ms 112528 KB Output is correct
53 Correct 118 ms 112920 KB Output is correct
54 Correct 117 ms 110956 KB Output is correct