Submission #920584

#	Time	Username	Problem	Language	Result	Execution time	Memory
920584		boris_mihov	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5054 ms	285076 KiB

street_lamps

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>

typedef long long llong;
const int MAXN = 300000 + 10;
const int MAXLOG = 19;
const int INF  = 1e9;

int n, q;
char a[MAXN];
char s[MAXN];
std::mt19937 rng(69420);

struct MergeSortTree
{
    struct Treap
    {
        struct Node
        {
            int sum;
            int val;
            int x, y;

            Node *left, *right;
        
            Node()
            {
                x = y = sum = 0;
                left = right = nullptr;
            }

            Node(int _x, int _val, int _y)
            {
                left = right = nullptr;
                sum = val = _val;
                x = _x;
                y = _y;
            }
        };

        Node *root;
        void recover(Node *curr)
        {
            if (curr == nullptr)
            {
                return;
            }

            curr->sum = curr->val;
            if (curr->left != nullptr)
            {
                curr->sum += curr->left->sum;
            }

            if (curr->right != nullptr)
            {
                curr->sum += curr->right->sum;
            }
        }

        void split(Node *curr, Node *&left, Node *&right, int value)
        {
            if (curr == nullptr)
            {
                left = right = nullptr;
                return;
            }

            if (curr->x <= value)
            {
                left = curr;
                split(curr->right, left->right, right, value);
                recover(left);
            } else
            {
                right = curr;
                split(curr->left, left, right->left, value);
                recover(right);
            }
        }

        void merge(Node *&curr, Node *left, Node *right)
        {
            if (left == nullptr)
            {
                curr = right;
                return;
            }

            if (right == nullptr)
            {
                curr = left;
                return;
            }

            if (left->y > right->y)
            {
                curr = left;
                merge(curr->right, left->right, right);
            } else
            {
                curr = right;
                merge(curr->left, left, right->left);
            }

            recover(curr);
        }

        void update(int x, int val)
        {
            Node *ll, *lr, *l, *r;
            split(root, l, r, x);
            split(l, ll, lr, x - 1);
            if (lr != nullptr)
            {
                lr->val += val;
                recover(lr);
            } else
            {
                lr = new Node(x, val, rng());
            }
            
            merge(l, ll, lr);
            merge(root, l, r);
        }

        int query(int from)
        {
            Node *l, *r;
            split(root, l, r, from - 1);
            int res = 0;

            if (r != nullptr)
            {
                res = r->sum;
            }

            merge(root, l, r);
            return res;
        }
    };

    Treap tree[4*MAXN];
    void update(int l, int r, int node, int queryRow, int queryCol, int queryVal)
    {
        tree[node].update(queryCol, queryVal);
        if (l == r)
        {
            return;
        }

        int mid = (l + r) / 2;
        if (queryRow <= mid) update(l, mid, 2*node, queryRow, queryCol, queryVal);
        else update(mid + 1, r, 2*node + 1, queryRow, queryCol, queryVal);
    }

    int query(int l, int r, int node, int queryRow, int queryCol)
    {
        if (l >= queryRow)
        {
            return tree[node].query(queryCol);
        }

        int mid = (l + r) / 2;
        int res = query(mid + 1, r, 2*node + 1, queryRow, queryCol);
        if (queryRow <= mid) res += query(l, mid, 2*node, queryRow, queryCol);
        return res;
    }

    void update(int row, int col, int val)
    {
        if (row == 0 || col == 0)
        {
            return;
        }

        update(1, n, 1, row, col, val);
    }

    int query(int row, int col)
    {
        return query(1, n, 1, row, col);
    }
};

struct Fenwick
{
    int tree[MAXN];
    void update(int pos, int val)
    {
        for (int idx = pos ; idx <= n ; idx += idx & (-idx))
        {
            tree[idx] += val;
        }
    }

    int query(int pos)
    {
        int res = 0;
        for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }

    int findKth(int k)
    {
        int pos = 0;
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (pos + (1 << log) <= n && tree[pos + (1 << log)] < k)
            {
                pos += (1 << log);
                k -= tree[pos];
            }
        }

        return pos + 1;
    }
};

Fenwick fenwick;
MergeSortTree tree;
void update(int fromX, int fromY, int toX, int toY, int val)
{
    fromX--; fromY--;
    tree.update(toX, toY, val);
    tree.update(fromX, toY, -val);
    tree.update(toX, fromY, -val);
    tree.update(fromX, fromY, val);
}

int query(int r, int c, int time)
{
    int res = tree.query(r, c);
    if (res < 0)
    {
        res += time;
    }
    
    return res;
}

void toggle(int idx, int time)
{
    int res = fenwick.query(idx);
    int lPos = 1;
    if (res - (s[idx] == '0') > 0)
    {
        lPos = fenwick.findKth(res - (s[idx] == '0')) + 1;
    }

    int rPos = fenwick.findKth(res + 1) - 1;
    update(lPos, idx, idx, rPos, (s[idx] == '1' ? time : -time));
    fenwick.update(idx, -(1 ^ (s[idx] - '0')));
    s[idx] = '0' + ('1' - s[idx]);
    fenwick.update(idx, (1 ^ (s[idx] - '0')));
}

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        s[i] = '0';
        fenwick.update(i, 1);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (a[i] == '1')
        {
            toggle(i, 1);
        }
    }

    char qType[7];
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> qType;

        if (qType[0] == 't')
        {
            int pos;
            std::cin >> pos;
            toggle(pos, i + 1);
        } else
        {
            int l, r;
            std::cin >> l >> r;
            std::cout << query(l, r - 1, i + 1) << '\n';
        }
    }
}

void input()
{
    std::cin >> n >> q;
    std::cin >> a + 1;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void input()':
street_lamps.cpp:303:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  303 |     std::cin >> a + 1;
      |                 ~~^~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20