Submission #920549

# Submission time Handle Problem Language Result Execution time Memory
920549 2024-02-02T17:47:13 Z boris_mihov Street Lamps (APIO19_street_lamps) C++17
0 / 100
5000 ms 290416 KB
#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;
            bool toggled;
            bool allToggles;
            int x, y;

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

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

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

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

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

        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;
                lr->toggled ^= 1;
                recover(lr);
            } else
            {
                lr = new Node(x, val, 1, rng());
            }
            
            merge(l, ll, lr);
            merge(root, l, r);
        }

        std::pair <int,bool> query(int from)
        {
            Node *l, *r;
            split(root, l, r, from - 1);
            int res = 0;
            bool toggled = 0;

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

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

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

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

        int mid = (l + r) / 2;
        std::pair <int,bool> res = query(mid + 1, r, 2*node + 1, queryRow, queryCol);
        if (queryRow <= mid) 
        {
            auto add = query(l, mid, 2*node, queryRow, queryCol);
            res.first += add.first;
            res.second ^= add.second;
        }

        return res;
    }

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

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

    std::pair <int,bool> 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)
{
    auto [res, myState] = tree.query(r, c);
    if (myState == 1)
    {
        res += time;
    }
    
    return res;
}

void toggle(int idx, int time)
{
    int res = fenwick.query(idx);
    int lPos = fenwick.findKth(res - (s[idx] == '0'));
    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, 0);
        }
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        std::string qType;
        std::cin >> qType;

        if (qType == "toggle")
        {
            int pos;
            std::cin >> pos;
            toggle(pos, i);
        } else
        {
            int l, r;
            std::cin >> l >> r;
            std::cout << query(l, r - 1, i) << '\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

street_lamps.cpp: In function 'void input()':
street_lamps.cpp:313:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  313 |     std::cin >> a + 1;
      |                 ~~^~~
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 527 ms 3484 KB Output is correct
2 Correct 865 ms 7280 KB Output is correct
3 Correct 1920 ms 14844 KB Output is correct
4 Execution timed out 5039 ms 290416 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 3164 KB Output is correct
2 Correct 8 ms 3164 KB Output is correct
3 Incorrect 9 ms 3308 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 4 ms 2908 KB Output is correct
2 Correct 6 ms 3164 KB Output is correct
3 Incorrect 8 ms 3164 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -