제출 #216481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216481		usachevd0	가로등 (APIO19_street_lamps)	C++14	60 / 100	579 ms	31092 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);
        }
    }
}

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

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

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