oj.uz

답안 #216506

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
216506 2020-03-27T12:05:12 Z usachevd0 가로등 (APIO19_street_lamps) C++14
100 / 100
 2585 ms 155152 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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