제출 #216506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216506		usachevd0	가로등 (APIO19_street_lamps)	C++14	100 / 100	2585 ms	155152 KiB

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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20