oj.uz

Submission #920582

# Submission time Handle Problem Language Result Execution time Memory
920582 2024-02-02T18:05:22 Z boris_mihov Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 283108 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

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

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

        if (qType == "toggle")
        {
            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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 3404 KB Output is correct
2 Correct 927 ms 3924 KB Output is correct
3 Correct 2009 ms 10180 KB Output is correct
4 Execution timed out 5042 ms 280076 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3164 KB Output is correct
2 Correct 8 ms 3076 KB Output is correct
3 Correct 8 ms 3164 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Execution timed out 5084 ms 222096 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2908 KB Output is correct
2 Correct 6 ms 2928 KB Output is correct
3 Correct 8 ms 3040 KB Output is correct
4 Correct 11 ms 3164 KB Output is correct
5 Correct 3339 ms 250348 KB Output is correct
6 Execution timed out 5054 ms 283108 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 580 ms 3404 KB Output is correct
9 Correct 927 ms 3924 KB Output is correct
10 Correct 2009 ms 10180 KB Output is correct
11 Execution timed out 5042 ms 280076 KB Time limit exceeded
12 Halted 0 ms 0 KB -