Submission #216482

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
216482	2020-03-27T11:05:06 Z	usachevd0	Street Lamps (APIO19_street_lamps)	C++14	80 / 100	596 ms	26864 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);
        }
    }
}

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

    int n, q;
    cin >> n >> q;
    if (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 (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 (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 (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();
        vector< pair<pii, int> > S;
        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));
                        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));
                        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));
                        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));
                        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));
                    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;
            }
//            debug(t);
//            out_blocks();
        }

//        for (auto e : S)
//            debug(e.fi.fi, e.fi.se, e.se);

        //
        int fnw[n + 1];
        memset(fnw, 0, sizeof(fnw));
        auto fadd = [&](int i, int d)
        {
            for (i = n - i; i <= n; i += i & -i)
                fnw[i] += d;
        };
        auto fgt = [&](int i)
        {
            int ans = 0;
            for (i = n - i; i >= 1; i -= i & -i)
                ans += fnw[i];
            return ans;
        };

        vector< pair<pii, pii> > Z;
        for (int t = 1; t <= q; ++t)
        {
            auto &q = que[t];
            if (q.se != -1)
            {
                int l = q.fi;
                int r = q.se;
                Z.push_back(mp(mp(l, r), mp(t, -1)));
            }
        }
        sort(all(S));
        sort(all(Z));
        int ptr1 = 0, ptr2 = 0;
        for (int l = 0; l < n; ++l)
        {
            while (ptr1 < S.size() && S[ptr1].fi.fi == l)
            {
                int R = S[ptr1].fi.se;
                int D = S[ptr1].se;
                ptr1++;
                fadd(R, D);
            }
            while (ptr2 < Z.size() && Z[ptr2].fi.fi == l)
            {
                int R = Z[ptr2].fi.se;
                Z[ptr2].se.se = fgt(R);
                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)
                {
                    Z[ptr2].se.se += Z[ptr2].se.fi - last_change;
                }
                ptr2++;
            }
        }
        sort(all(Z), [&](pair<pii, pii> p1, pair<pii, pii> p2) -> bool
        {
            return p1.se.fi < p2.se.fi;
        });
        for (auto e : Z)
            cout << e.se.se << '\n';

        exit(0);
    }

    return 0;
}

Compilation message

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:318: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:334:43: warning: statement has no effect [-Wunused-value]
                 debug(bg, sz, last_change);
                                           ^
street_lamps.cpp:331:21: warning: unused variable 'bg' [-Wunused-variable]
                 int bg = block.fi.fi;
                     ^~
street_lamps.cpp:332:21: warning: unused variable 'sz' [-Wunused-variable]
                 int sz = block.fi.se;
                     ^~
street_lamps.cpp:333:21: warning: unused variable 'last_change' [-Wunused-variable]
                 int last_change = block.se;                
                     ^~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:446:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (ptr1 < S.size() && S[ptr1].fi.fi == l)
                    ~~~~~^~~~~~~~~~
street_lamps.cpp:453:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (ptr2 < Z.size() && Z[ptr2].fi.fi == l)
                    ~~~~~^~~~~~~~~~
street_lamps.cpp:325: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	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	3596 KB	Output is correct
2	Correct	88 ms	3704 KB	Output is correct
3	Correct	89 ms	3704 KB	Output is correct
4	Correct	137 ms	7748 KB	Output is correct
5	Correct	117 ms	7948 KB	Output is correct
6	Correct	108 ms	7564 KB	Output is correct
7	Correct	134 ms	7560 KB	Output is correct
8	Correct	166 ms	8968 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	4480 KB	Output is correct
2	Correct	8 ms	4480 KB	Output is correct
3	Correct	8 ms	4608 KB	Output is correct
4	Correct	10 ms	4480 KB	Output is correct
5	Correct	84 ms	9868 KB	Output is correct
6	Correct	113 ms	10124 KB	Output is correct
7	Correct	146 ms	10252 KB	Output is correct
8	Correct	184 ms	11912 KB	Output is correct
9	Correct	95 ms	7288 KB	Output is correct
10	Correct	94 ms	7420 KB	Output is correct
11	Correct	95 ms	7544 KB	Output is correct
12	Correct	182 ms	10504 KB	Output is correct
13	Correct	182 ms	11916 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	6 ms	512 KB	Output is correct
5	Correct	252 ms	17868 KB	Output is correct
6	Correct	320 ms	19588 KB	Output is correct
7	Correct	424 ms	24028 KB	Output is correct
8	Correct	596 ms	26864 KB	Output is correct
9	Correct	206 ms	19104 KB	Output is correct
10	Correct	191 ms	21152 KB	Output is correct
11	Correct	209 ms	19108 KB	Output is correct
12	Correct	189 ms	21152 KB	Output is correct
13	Correct	207 ms	19108 KB	Output is correct
14	Correct	188 ms	21152 KB	Output is correct
15	Correct	174 ms	10508 KB	Output is correct
16	Correct	184 ms	11916 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	83 ms	3596 KB	Output is correct
9	Correct	88 ms	3704 KB	Output is correct
10	Correct	89 ms	3704 KB	Output is correct
11	Correct	137 ms	7748 KB	Output is correct
12	Correct	117 ms	7948 KB	Output is correct
13	Correct	108 ms	7564 KB	Output is correct
14	Correct	134 ms	7560 KB	Output is correct
15	Correct	166 ms	8968 KB	Output is correct
16	Correct	7 ms	4480 KB	Output is correct
17	Correct	8 ms	4480 KB	Output is correct
18	Correct	8 ms	4608 KB	Output is correct
19	Correct	10 ms	4480 KB	Output is correct
20	Correct	84 ms	9868 KB	Output is correct
21	Correct	113 ms	10124 KB	Output is correct
22	Correct	146 ms	10252 KB	Output is correct
23	Correct	184 ms	11912 KB	Output is correct
24	Correct	95 ms	7288 KB	Output is correct
25	Correct	94 ms	7420 KB	Output is correct
26	Correct	95 ms	7544 KB	Output is correct
27	Correct	182 ms	10504 KB	Output is correct
28	Correct	182 ms	11916 KB	Output is correct
29	Correct	5 ms	384 KB	Output is correct
30	Correct	5 ms	384 KB	Output is correct
31	Correct	5 ms	384 KB	Output is correct
32	Correct	6 ms	512 KB	Output is correct
33	Correct	252 ms	17868 KB	Output is correct
34	Correct	320 ms	19588 KB	Output is correct
35	Correct	424 ms	24028 KB	Output is correct
36	Correct	596 ms	26864 KB	Output is correct
37	Correct	206 ms	19104 KB	Output is correct
38	Correct	191 ms	21152 KB	Output is correct
39	Correct	209 ms	19108 KB	Output is correct
40	Correct	189 ms	21152 KB	Output is correct
41	Correct	207 ms	19108 KB	Output is correct
42	Correct	188 ms	21152 KB	Output is correct
43	Correct	174 ms	10508 KB	Output is correct
44	Correct	184 ms	11916 KB	Output is correct
45	Incorrect	48 ms	3832 KB	Output isn't correct
46	Halted	0 ms	0 KB	-