Submission #216506

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
216506	2020-03-27T12:05:12 Z	usachevd0	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2585 ms	155152 KB

street_lamps

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;

void debug_out()
{
    cerr << endl;
}

template<typename T1, typename... T2> void debug_out(T1 A, T2... B)
{
    cerr << ' ' << A;
    debug_out(B...);
}

#ifdef DEBUG
    #define time(...) 42
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 42
#endif

template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }

mt19937 rng(time(0));
const int INF32 = 1e9;
const int maxN = 300005;
char a0[maxN];
pii que[maxN];

namespace btrp
{
    struct Node
    {
        int y;
        int bg, sz, last_change;
        Node *l, *r;

        Node() {}
        Node(int _bg, int _sz, int _last_change): bg(_bg), sz(_sz), last_change(_last_change), y(rng()), l(0), r(0) {}
    };

    Node* merge(Node *a, Node *b)
    {
        if (!a) return b;
        if (!b) return a;
        if (a->y > b->y)
        {
            a->r = merge(a->r, b);
            return a;
        }
        else
        {
            b->l = merge(a, b->l);
            return b;
        }
    }

    pair<Node*, Node*> split(Node *t, int x)
    {
        if (!t) return {0, 0};
        if (t->bg < x)
        {
            auto p = split(t->r, x);
            t->r = p.fi;
            return {t, p.se};
        }
        else
        {
            auto p = split(t->l, x);
            t->l = p.se;
            return {p.fi, t};
        }
    }

    void add(Node *&t, int bg, int sz, int last_change)
    {
        auto p = split(t, bg);
        t = merge(p.fi, merge(new Node(bg, sz, last_change), p.se));
    }

    void rem(Node *&t, int x)
    {
        if (!t) return;
        if (t->bg == x)
        {
            t = merge(t->l, t->r);
            return;
        }
        if (t->bg < x)
            rem(t->r, x);
        else
            rem(t->l, x);
    }

    pair<pii, int> gt(Node *t, int x)
    {
        if (!t) return {{INF32, INF32}, INF32};
        if (t->bg <= x)
        {
            auto res = gt(t->r, x);
            if (res.fi.fi > x)
                return {{t->bg, t->sz}, t->last_change};
            else
                return res;
        }
        else
        {
            return gt(t->l, x);
        }
    }

    void travel(Node *t, vector< pair<pii, int> > &a)
    {
        if (t)
        {
            travel(t->l, a);
            a.push_back(mp(mp(t->bg, t->sz), t->last_change));
            travel(t->r, a);
        }
    }
}

struct fenwick
{
    int n;
    vector<int> f;

    fenwick() {}
    void init(int _n)
    {
        n = _n;
        f.assign(n + 1, 0);
    }

    void add(int i, int d)
    {
        for (i = n - i; i <= n; i += i & -i)
            f[i] += d;
    }

    int gt(int i)
    {
        int ans = 0;
        for (i = n - i; i >= 1; i -= i & -i)
            ans += f[i];
        return ans;
    }
};

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    if (0&&n <= 100 && q <= 100)
    {
        char t[q + 1][n];
        memset(t, 0, sizeof(t));
        string s;
        cin >> s;
        for (int i = 0; i < n; ++i) t[0][i] = s[i] - '0';
        for (int i = 1; i <= q; ++i)
        {
            memcpy(t[i], t[i - 1], sizeof(t[i]));
            string cmd;
            cin >> cmd;
            if (cmd == "toggle")
            {
                int j;
                cin >> j;
                --j;
                t[i][j] ^= 1;
            }
            else
            {
                int l, r;
                cin >> l >> r;
                r -= 2;
                l--;
                int ans = 0;
                for (int u = 0; u < i; ++u)
                {
                    bool ok = true;
                    for (int j = l; j <= r; ++j)
                    {
                        ok &= t[u][j];
                    }
                    if (ok) ++ans;
                }
                cout << ans << '\n';
            }
        }
        exit(0);
    }
    // normal
    string tmp;
    cin >> tmp;
    for (int i = 0; i < n; ++i) a0[i] = tmp[i] - '0';
    bool all_ones = true;
    bool toggle_to_one = true;
    int last_toggle = -1;
    int first_query = -1;
    int _a[n];
    for (int i = 0; i < n; ++i) _a[i] = a0[i];
    for (int t = 1; t <= q; ++t)
    {
        string cmd;
        cin >> cmd;
        auto &q = que[t];
        if (cmd == "toggle")
        {
            last_toggle = t;
            q.se = -1;
            cin >> q.fi;
            q.fi--;
            int i = q.fi;
            _a[i] ^= 1;
            toggle_to_one &= _a[i] == 1;
        }
        else
        {
            if (first_query == -1) first_query = t;
            cin >> q.fi >> q.se;
            q.fi--;
            q.se -= 2;
            all_ones &= q.fi == q.se;
        }
    }
    if (0&&all_ones)
    {
        int when[n], sum[n];
        memset(when, 0, sizeof(when));
        memset(sum, 0, sizeof(sum));
        for (int t = 1; t <= q; ++t)
        {
            auto &q = que[t];
            if (q.se == -1)
            {
                int i = q.fi;
                if (a0[i] == 0)
                {
                    when[i] = t;
                }
                else
                {
                    sum[i] += t - when[i];
                }
                a0[i] ^= 1;
            }
            else
            {
                int i = q.fi;
                cout << sum[i] + (a0[i] == 1 ? t - when[i] : 0) << '\n';
            }
        }
        exit(0);
    }
    if (0&&toggle_to_one)
    {
        int when[n];
        for (int i = 0; i < n; ++i)
            if (a0[i] == 1)
                when[i] = 0;
            else
                when[i] = INF32;
        for (int t = 1; t <= q; ++t)
        {
            auto &q = que[t];
            if (q.se == -1)
            {
                int i = q.fi;
                when[i] = t;
            }
        }
        const int logN = 19;
        const int N = 1 << logN;
        int sgt[2 * N];
        fill(sgt, sgt + 2 * N, -INF32);
        for (int i = 0; i < n; ++i)
        {
            sgt[i + N] = when[i];
        }
        for (int v = N - 1; v >= 1; --v)
        {
            sgt[v] = max(sgt[v << 1], sgt[v << 1 | 1]);
        }
        for (int t = 1; t <= q; ++t)
        {
            auto &q = que[t];
            if (q.se != -1)
            {
                int l = q.fi;
                int r = q.se;
                int mx = -1e9;
                for (l += N, r += N; l <= r; l >>= 1, r >>= 1)
                {
                    if (l & 1)  chkmax(mx, sgt[l++]);
                    if (~r & 1) chkmax(mx, sgt[r--]);
                }
                cout << max(0, t - mx) << '\n';
            }
        }
        exit(0);
    }
    if (first_query == -1)
    {
        exit(0);
    }
    if (1||last_toggle < first_query)
    {
        btrp::Node* blocks = 0;
        int cur_bg = -1, cur_sz = -1;
        for (int i = 0; i <= n; ++i)
        {
            if (i < n && a0[i] == 1)
            {
                if (i == 0 || a0[i - 1] == 0)
                {
                    cur_bg = i;
                    cur_sz = 1;
                }
                else ++cur_sz;
            }
            else
            {
                if (cur_bg != -1 && (i == n || i > 0 && a0[i - 1] == 1))
                {
                    btrp::add(blocks, cur_bg, cur_sz, 0);
                    cur_bg = -1;
                }
            }
        }
        auto out_blocks = [&]
        {
            vector< pair<pii, int> > remaining_blocks;
            btrp::travel(blocks, remaining_blocks);
            for (auto block : remaining_blocks)
            {
                int bg = block.fi.fi;
                int sz = block.fi.se;
                int last_change = block.se;                
                debug(bg, sz, last_change);
            }
        };
//        out_blocks();

        const int logN = 19;
        const int NN = 1 << logN;
        vector<int> rights[2 * NN];
        fenwick fnw[2 * NN];
        for (int t = 1; t <= q; ++t)
        {
            auto &q = que[t];
            if (q.se != -1)
            {
                int l = q.fi;
                int r = q.se;
                for (int v = l + NN; v >= 1; v >>= 1)
                    rights[v].push_back(r);
            }
        }
        for (int v = 1; v < 2 * NN; ++v)
        {
            sort(all(rights[v]));
            rights[v].resize(unique(all(rights[v])) - rights[v].begin());
            fnw[v].init(rights[v].size());
        }
        auto mdf2 = [&](int v, int R, int d)
        {
            int sz = rights[v].size();
            int i = (upper_bound(all(rights[v]), R) - rights[v].begin()) - 1;
            if (0 <= i && i < sz)
            {
                fnw[v].add(i, d);
            }
        };
        function< void(int, int, int, int, int, int, int) > mdf1 = [&](int v, int vl, int vr, int l, int r, int d, int R)
        {
            if (l > r || vr < l || r < vl) return;
            if (l <= vl && vr <= r)
            {
                mdf2(v, R, d);
                return;
            }
            int vm = (vl + vr) >> 1;
            mdf1(v << 1, vl, vm, l, r, d, R);
            mdf1(v << 1 | 1, vm + 1, vr, l, r, d, R);
        };
        auto mdf = [&](int L, int R, int d)
        {
            if (L >= n) return;
            mdf1(1, 0, NN - 1, L, n - 1, d, R);
            /*
            int v = 1, vl = 0, vr = NN - 1;
            while (true)
            {
                int vm = (vl + vr) >> 1;
                if (vl == vr)
                {
                    if (vl >= L)
                        mdf2(v, R, d);
                    break;
                }
                if (L > vm + 1)
                {
                    v = v << 1 | 1;
                    vl = vm + 1;
                }
                else
                {
                    mdf2(v, R, d);
                    if (L <= vm)
                    {
                        v <<= 1;
                        vr = vm;
                    }
                    else
                    {
                        break;
                    }
                }
            }/**/
        };
        for (int t = 1; t <= q; ++t)
        {
            auto &q = que[t];
            if (q.se == -1)
            {
                int i = q.fi;
                if (a0[i] == 0)
                {
                    bool Left = (i > 0 && a0[i - 1] == 1);
                    bool Right = (i + 1 < n && a0[i + 1] == 1);
                    if (!Left && !Right)
                    {
                        btrp::add(blocks, i, 1, t);
                    }
                    if (Left && !Right)
                    {
                        auto block = btrp::gt(blocks, i - 1);
                        int bg = block.fi.fi;
                        int sz = block.fi.se;
                        int last_change = block.se;
//                        S.push_back(mp(mp(bg, bg + sz - 1), t - last_change));
                        mdf(bg, bg + sz - 1, t - last_change);
                        btrp::rem(blocks, bg);
                        btrp::add(blocks, bg, sz + 1, t);                        
                    }
                    if (!Left && Right)
                    {
                        auto block = btrp::gt(blocks, i + 1);
                        int bg = block.fi.fi;
                        int sz = block.fi.se;
                        int last_change = block.se;
//                        S.push_back(mp(mp(bg, bg + sz - 1), t - last_change));
                        mdf(bg, bg + sz - 1, t - last_change);
                        btrp::rem(blocks, bg);
                        btrp::add(blocks, bg - 1, sz + 1, t);
                    }
                    if (Left && Right)
                    {
                        auto block1 = btrp::gt(blocks, i - 1);
                        int bg1 = block1.fi.fi;
                        int sz1 = block1.fi.se;
                        int last_change1 = block1.se;
//                        S.push_back(mp(mp(bg1, bg1 + sz1 - 1), t - last_change1));
                        mdf(bg1, bg1 + sz1 - 1, t - last_change1);
                        btrp::rem(blocks, bg1);

                        auto block2 = btrp::gt(blocks, i + 1);
                        int bg2 = block2.fi.fi;
                        int sz2 = block2.fi.se;
                        int last_change2 = block2.se;
//                        S.push_back(mp(mp(bg2, bg2 + sz2 - 1), t - last_change2));
                        mdf(bg2, bg2 + sz2 - 1, t - last_change2);
                        btrp::rem(blocks, bg2);

                        btrp::add(blocks, bg1, sz1 + 1 + sz2, t);
                    }
                }
                else
                {
                    pair<pii, int> block = btrp::gt(blocks, i);
                    int bg = block.fi.fi;
                    int sz = block.fi.se;
                    int last_change = block.se;
//                    S.push_back(mp(mp(bg, bg + sz - 1), t - last_change));
                    mdf(bg, bg + sz - 1, t - last_change);
                    btrp::rem(blocks, bg);
                    if (i > bg)
                        btrp::add(blocks, bg, i - bg, t);
                    if (i < bg + sz - 1)
                        btrp::add(blocks, i + 1, (bg + sz - 1) - (i + 1) + 1, t);
                }
                a0[i] ^= 1;
            }
            else
            {
                int l = q.fi;
                int r = q.se;
                int ans = 0;
                auto block = btrp::gt(blocks, l);
                int bg = block.fi.fi;
                int sz = block.fi.se;
                int last_change = block.se;
                if (bg != INF32 && r <= bg + sz - 1)
                {
                    ans += t - last_change;
                }

                for (int v = l + NN; v >= 1; v >>= 1)
                {
                    int i = lower_bound(all(rights[v]), r) - rights[v].begin();
                    ans += fnw[v].gt(i);
                }
                cout << ans << '\n';
            }
//            debug(t);
//            out_blocks();
        }

        exit(0);
    }

    return 0;
}

Compilation message

street_lamps.cpp:441:14: warning: "/*" within comment [-Wcomment]
             }/**/
               
street_lamps.cpp: In constructor 'btrp::Node::Node(int, int, int)':
street_lamps.cpp:49:21: warning: 'btrp::Node::last_change' will be initialized after [-Wreorder]
         int bg, sz, last_change;
                     ^~~~~~~~~~~
street_lamps.cpp:48:13: warning:   'int btrp::Node::y' [-Wreorder]
         int y;
             ^
street_lamps.cpp:53:9: warning:   when initialized here [-Wreorder]
         Node(int _bg, int _sz, int _last_change): bg(_bg), sz(_sz), last_change(_last_change), y(rng()), l(0), r(0) {}
         ^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:345:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 if (cur_bg != -1 && (i == n || i > 0 && a0[i - 1] == 1))
                                                ~~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In lambda function:
street_lamps.cpp:361:43: warning: statement has no effect [-Wunused-value]
                 debug(bg, sz, last_change);
                                           ^
street_lamps.cpp:358:21: warning: unused variable 'bg' [-Wunused-variable]
                 int bg = block.fi.fi;
                     ^~
street_lamps.cpp:359:21: warning: unused variable 'sz' [-Wunused-variable]
                 int sz = block.fi.se;
                     ^~
street_lamps.cpp:360:21: warning: unused variable 'last_change' [-Wunused-variable]
                 int last_change = block.se;                
                     ^~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:352:14: warning: variable 'out_blocks' set but not used [-Wunused-but-set-variable]
         auto out_blocks = [&]
              ^~~~~~~~~~

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	90616 KB	Output is correct
2	Correct	71 ms	90616 KB	Output is correct
3	Correct	72 ms	90616 KB	Output is correct
4	Correct	71 ms	90744 KB	Output is correct
5	Correct	78 ms	90640 KB	Output is correct
6	Correct	72 ms	90644 KB	Output is correct
7	Correct	74 ms	90616 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	495 ms	114900 KB	Output is correct
2	Correct	564 ms	114816 KB	Output is correct
3	Correct	811 ms	115820 KB	Output is correct
4	Correct	1848 ms	137356 KB	Output is correct
5	Correct	2115 ms	142052 KB	Output is correct
6	Correct	1584 ms	133124 KB	Output is correct
7	Correct	2146 ms	148464 KB	Output is correct
8	Correct	2144 ms	149852 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	90744 KB	Output is correct
2	Correct	75 ms	90748 KB	Output is correct
3	Correct	75 ms	90872 KB	Output is correct
4	Correct	74 ms	90872 KB	Output is correct
5	Correct	842 ms	111244 KB	Output is correct
6	Correct	1499 ms	128988 KB	Output is correct
7	Correct	2047 ms	141444 KB	Output is correct
8	Correct	2271 ms	154236 KB	Output is correct
9	Correct	455 ms	115176 KB	Output is correct
10	Correct	493 ms	117676 KB	Output is correct
11	Correct	525 ms	117152 KB	Output is correct
12	Correct	2265 ms	152440 KB	Output is correct
13	Correct	2297 ms	154124 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	75 ms	90872 KB	Output is correct
2	Correct	82 ms	90848 KB	Output is correct
3	Correct	85 ms	90728 KB	Output is correct
4	Correct	71 ms	90744 KB	Output is correct
5	Correct	2585 ms	155152 KB	Output is correct
6	Correct	2118 ms	145268 KB	Output is correct
7	Correct	1555 ms	133120 KB	Output is correct
8	Correct	924 ms	114092 KB	Output is correct
9	Correct	511 ms	112164 KB	Output is correct
10	Correct	367 ms	108152 KB	Output is correct
11	Correct	529 ms	112292 KB	Output is correct
12	Correct	360 ms	108280 KB	Output is correct
13	Correct	519 ms	112036 KB	Output is correct
14	Correct	364 ms	108152 KB	Output is correct
15	Correct	2257 ms	151660 KB	Output is correct
16	Correct	2260 ms	152788 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	90616 KB	Output is correct
2	Correct	71 ms	90616 KB	Output is correct
3	Correct	72 ms	90616 KB	Output is correct
4	Correct	71 ms	90744 KB	Output is correct
5	Correct	78 ms	90640 KB	Output is correct
6	Correct	72 ms	90644 KB	Output is correct
7	Correct	74 ms	90616 KB	Output is correct
8	Correct	495 ms	114900 KB	Output is correct
9	Correct	564 ms	114816 KB	Output is correct
10	Correct	811 ms	115820 KB	Output is correct
11	Correct	1848 ms	137356 KB	Output is correct
12	Correct	2115 ms	142052 KB	Output is correct
13	Correct	1584 ms	133124 KB	Output is correct
14	Correct	2146 ms	148464 KB	Output is correct
15	Correct	2144 ms	149852 KB	Output is correct
16	Correct	72 ms	90744 KB	Output is correct
17	Correct	75 ms	90748 KB	Output is correct
18	Correct	75 ms	90872 KB	Output is correct
19	Correct	74 ms	90872 KB	Output is correct
20	Correct	842 ms	111244 KB	Output is correct
21	Correct	1499 ms	128988 KB	Output is correct
22	Correct	2047 ms	141444 KB	Output is correct
23	Correct	2271 ms	154236 KB	Output is correct
24	Correct	455 ms	115176 KB	Output is correct
25	Correct	493 ms	117676 KB	Output is correct
26	Correct	525 ms	117152 KB	Output is correct
27	Correct	2265 ms	152440 KB	Output is correct
28	Correct	2297 ms	154124 KB	Output is correct
29	Correct	75 ms	90872 KB	Output is correct
30	Correct	82 ms	90848 KB	Output is correct
31	Correct	85 ms	90728 KB	Output is correct
32	Correct	71 ms	90744 KB	Output is correct
33	Correct	2585 ms	155152 KB	Output is correct
34	Correct	2118 ms	145268 KB	Output is correct
35	Correct	1555 ms	133120 KB	Output is correct
36	Correct	924 ms	114092 KB	Output is correct
37	Correct	511 ms	112164 KB	Output is correct
38	Correct	367 ms	108152 KB	Output is correct
39	Correct	529 ms	112292 KB	Output is correct
40	Correct	360 ms	108280 KB	Output is correct
41	Correct	519 ms	112036 KB	Output is correct
42	Correct	364 ms	108152 KB	Output is correct
43	Correct	2257 ms	151660 KB	Output is correct
44	Correct	2260 ms	152788 KB	Output is correct
45	Correct	282 ms	106448 KB	Output is correct
46	Correct	380 ms	107676 KB	Output is correct
47	Correct	1076 ms	120144 KB	Output is correct
48	Correct	1835 ms	141300 KB	Output is correct
49	Correct	546 ms	122412 KB	Output is correct
50	Correct	537 ms	122340 KB	Output is correct
51	Correct	578 ms	122528 KB	Output is correct
52	Correct	649 ms	124852 KB	Output is correct
53	Correct	643 ms	124612 KB	Output is correct
54	Correct	643 ms	124612 KB	Output is correct