oj.uz

Submission #859494

# Submission time Handle Problem Language Result Execution time Memory
859494 2023-10-10T08:43:26 Z normankr07 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 1749 ms 228320 KB 
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;
const int maxn = 3e5 + 5;
int n, q;
char c[maxn];
int nodes[maxn * 4];
int f[maxn];
set<int> st;

void build(int id, int l, int r)
{
    if (l == r)
    {
        if (c[l] == '1')
            nodes[id] = 0;
        else
            nodes[id] = q + 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    nodes[id] = max(nodes[id * 2], nodes[id * 2 + 1]);
}

void update(int id, int l, int r, int i, int val)
{
    if (i < l || i > r)
        return;
    if (l == r)
    {
        nodes[id] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (i <= mid)
        update(id * 2, l, mid, i, val);
    else
        update(id * 2 + 1, mid + 1, r, i, val);
    nodes[id] = max(nodes[id * 2], nodes[id * 2 + 1]);
}

int get(int id, int l, int r, int u, int v)
{
    if (v < l || r < u)
        return 0;
    if (u <= l && r <= v)
        return nodes[id];
    int mid = (l + r) >> 1;
    return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}

struct node
{
    int l, r, val;
};

vector<node> bit[2][maxn];
int cnt[2][maxn];

void createl(int x, int id1, int id)
{
    if (bit[x][id1][id].l == 0)
    {
        bit[x][id1][id].l = ++cnt[x][id1];
        bit[x][id1].push_back({0, 0});
    }
}

void creater(int x, int id1, int id)
{
    if (bit[x][id1][id].r == 0)
    {
        bit[x][id1][id].r = ++cnt[x][id1];
        bit[x][id1].push_back({0, 0});
    }
}

void update1(int id1, int id, int l, int r, int i, int val, int x)
{
    if (i < l || i > r)
        return;
    int mid = (l + r) >> 1;
    if (i <= mid)
        createl(x, id1, id);
    else
        creater(x, id1, id);
    bit[x][id1][id].val += val;
    if (l == r)
        return;
    if (i <= mid)
        update1(id1, bit[x][id1][id].l, l, mid, i, val, x);
    else
        update1(id1, bit[x][id1][id].r, mid + 1, r, i, val, x);
}

int get1(int id1, int id, int l, int r, int i, int x)
{
    if (i < l || i > r)
        return 0;
    int mid = (l + r) >> 1;
    if (l == r)
        return bit[x][id1][id].val;
    if (i <= mid && bit[x][id1][id].l)
        return get1(id1, bit[x][id1][id].l, l, mid, i, x);
    else if (i > mid && bit[x][id1][id].r)
    {
        if (bit[x][id1][id].l)
            return bit[x][id1][bit[x][id1][id].l].val + get1(id1, bit[x][id1][id].r, mid + 1, r, i, x);
        return get1(id1, bit[x][id1][id].r, mid + 1, r, i, x);
    }
    else if (i > mid && bit[x][id1][id].l)
        return bit[x][id1][bit[x][id1][id].l].val;
    return 0;
}

void updatebt(int id, int i, int j, int val)
{
    for (int i1 = i; i1 <= n + 1; i1 += (i1 & -i1))
        update1(i1, 0, 1, n + 1, j, val, id);
}

int getbt(int id, int i, int j)
{
    int ans = 0;
    for (int i1 = i; i1 >= 1; i1 -= (i1 & -i1))
        ans += get1(i1, 0, 1, n + 1, j, id);
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> c[i];
    for (int i = 1; i <= n + 1; ++i)
    {
        bit[0][i].push_back({0, 0, 0});
    }
    st.insert(0);
    st.insert(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        if (c[i] == '1')
            f[i] = 0;
        else
            f[i] = q + 1;
        if (c[i] == '0')
            st.insert(i);
    }
    build(1, 1, n);
    for (int id = 1; id <= q; ++id)
    {
        int d, x, y;
        string s;
        cin >> s;
        if (s == "toggle")
            d = 2;
        else
            d = 1;
        if (d == 1)
        {
            cin >> x >> y;
            if (x > y)
                swap(x, y);
            int ans = get(1, 1, n, x, y - 1);
            if (ans == q + 1)
                cout << getbt(0, x, y) << '\n';
            else
                cout << getbt(0, x, y) + id - ans << '\n';
            continue;
        }
        cin >> x;
        if (c[x] == '0')
        {
            c[x] = '1';
            f[x] = id;
            update(1, 1, n, x, id);
            st.erase(x);
        }
        else
        {
            c[x] = '0';
            auto it = st.lower_bound(x);
            int dy = *it;
            int dx = *(--it);
            int tmp = id - f[x];
            updatebt(0, dx + 1, x + 1, tmp);
            updatebt(0, x + 1, x + 1, -tmp);
            updatebt(0, dx + 1, dy + 1, -tmp);
            updatebt(0, x + 1, dy + 1, tmp);
            f[x] = q + 1;
            update(1, 1, n, x, q + 1);
            st.insert(x);
        }
    }
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 17852 KB Output is correct
2 Correct 203 ms 17940 KB Output is correct
3 Correct 355 ms 22792 KB Output is correct
4 Correct 1155 ms 161144 KB Output is correct
5 Correct 271 ms 36120 KB Output is correct
6 Correct 1263 ms 174104 KB Output is correct
7 Correct 293 ms 44116 KB Output is correct
8 Correct 225 ms 31808 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 16728 KB Output is correct
4 Correct 4 ms 16728 KB Output is correct
5 Correct 296 ms 43348 KB Output is correct
6 Correct 329 ms 39628 KB Output is correct
7 Correct 270 ms 35496 KB Output is correct
8 Correct 244 ms 31572 KB Output is correct
9 Correct 79 ms 17544 KB Output is correct
10 Correct 96 ms 17656 KB Output is correct
11 Correct 90 ms 17748 KB Output is correct
12 Correct 311 ms 44116 KB Output is correct
13 Correct 266 ms 31824 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 5 ms 16988 KB Output is correct
4 Correct 5 ms 17244 KB Output is correct
5 Correct 302 ms 43056 KB Output is correct
6 Correct 744 ms 129740 KB Output is correct
7 Correct 1206 ms 174408 KB Output is correct
8 Correct 1749 ms 228320 KB Output is correct
9 Incorrect 227 ms 17440 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16732 KB Output isn't correct
2 Halted 0 ms 0 KB -