oj.uz

Submission #729914

# Submission time Handle Problem Language Result Execution time Memory
729914 2023-04-24T20:18:38 Z danikoynov Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2094 ms 193040 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 3e5 + 10;

struct BIT
{
    vector < int > ip[maxn], bit[maxn];

    void init()
    {
        for (int i = 0; i < maxn; i ++)
        {
            ip[i].push_back(0);
            sort(ip[i].begin(), ip[i].end());

            ip[i].resize(unique(ip[i].begin(), ip[i].end()) - ip[i].begin());
            bit[i].resize(ip[i].size());
        }
    }

    void add_init(int x, int y)
    {
        for (int i = x; i < maxn; i += (i & -i))
            ip[i].push_back(y);
    }

    void add(int x, int y, int v)
    {

        ///cout << "start" << endl;
        for (int i = x; i < maxn; i += (i & -i))
        {
            ///cout << ip[i][0] << endl;
            int y2 = lower_bound(ip[i].begin(), ip[i].end(), y) - ip[i].begin();
            for (int j = y2; j < bit[i].size(); j += (j & -j))
                bit[i][j] += v;
        }
        /// cout << "fine" << endl;

    }

    int query(int x, int y)
    {
        int ret = 0;
        for (int i = x; i > 0; i -= (i & -i))
        {
            int y2 = upper_bound(ip[i].begin(), ip[i].end(), y) - ip[i].begin() - 1;

            for (int j = y2; j > 0; j -= (j & -j))
            {
                ///cout << bit[i][j] << endl;
                ret = ret + bit[i][j];
            }
        }
        return ret;
    }
} bit;
struct interval
{
    int left, right, in_time;


    interval(int _left = 0, int _right = 0, int _in_time = 0)
    {
        left = _left;
        right = _right;
        in_time = _in_time;
    }

    bool operator < (const interval &it) const
    {
        if (left == it.left)
        {
            if (right == it.right)
                return in_time < it.in_time;
            return right < it.right;
        }
        return left < it.left;
    }
};

struct base_query
{
    string type;
    int x, a, b;
} base_ask[maxn];

int n, q, add_ans[maxn];
char c[maxn], cs[maxn];

void input()
{
    cin >> n >> q;
    n ++;
    for (int i = 1; i < n; i ++)
        cin >> c[i], cs[i] = c[i];
    for (int i = 1; i <= q; i ++)
    {
        cin >> base_ask[i].type;
        if (base_ask[i].type == "query")
        {
            cin >> base_ask[i].a >> base_ask[i].b;
        }
        else
        {
            cin >> base_ask[i].x;
        }
    }
}

set < pair < int, int > > available;
interval bef1[maxn], aft1[maxn], cur1[maxn];
void create_intervals()
{
    set < interval > st;
    int beg = 1;
    for (int i = 1; i < n; i ++)
    {
        if (c[i] == '0')
        {
            ///cout << beg << " -- " << i << endl;
            st.insert(interval(beg, i, 0));
            available.insert({beg, i});
            beg = i + 1;
        }
    }
    st.insert(interval(beg, n, 0));
    available.insert({beg, n});

    for (int i = 1; i <= q; i ++)
    {
        if (base_ask[i].type == "toggle")
        {
            int pos = base_ask[i].x;
            if (c[pos] == '0')
            {
                c[pos] = '1';
                set < interval > :: iterator aft_it = st.lower_bound(interval(pos + 1, pos + 1, -1));
                set < interval > :: iterator bef_it = prev(aft_it);
                interval bef = *bef_it;
                interval aft = *aft_it;
                interval cur(bef.left, aft.right, i);
                st.erase(bef);
                st.erase(aft);
                st.insert(cur);
                bef1[i] = bef;
                aft1[i] = aft;
                cur1[i] = cur;
                available.insert({cur.left, cur.right});
            }
            else
            {
                c[pos] = '0';
                set < interval > :: iterator cur_it = prev(st.lower_bound(interval(pos + 1, pos + 1, -1)));
                interval cur = *cur_it;
                interval bef(cur.left, pos, i);
                interval aft(pos + 1, cur.right, i);
                st.erase(cur);
                st.insert(bef);
                st.insert(aft);
                bef1[i] = bef;
                aft1[i] = aft;
                cur1[i] = cur;
                available.insert({bef.left, bef.right});
                available.insert({aft.left, aft.right});
            }
        }
        else
        {
            int pos = base_ask[i].a;
            set < interval > :: iterator cur_it = prev(st.upper_bound(interval(pos, n + 1, -1)));
            if (cur_it -> right >= base_ask[i].b)
                add_ans[i] = i - cur_it -> in_time;
        }

    }


    //for (pair < int, int > cur : available)
    //  cout << cur.first << " : " << cur.second << endl;
}

unordered_map < int, int > act[maxn], act_time[maxn];
void update_interval(interval cur, int cur_time)
{
    if (cur.left == cur.right)
        return;
    ///cout << "update " << cur.left << " " << cur.right << endl;
    if (act[cur.left][cur.right])
    {
        act[cur.left][cur.right] = 0;
        bit.add(cur.left, cur.right, cur_time - act_time[cur.left][cur.right]);
    }
    else
    {

        act_time[cur.left][cur.right] = cur_time;
        act[cur.left][cur.right] = 1;
    }
}

void build_trees()
{
    for (pair < int, int > cur : available)
    {
        if (cur.first != cur.second)
        {
            bit.add_init(cur.first, cur.second);
        }
    }
    bit.init();

}

int query(int a, int b)
{
    return bit.query(a, n) - bit.query(a, b - 1);
}
void simulate()
{

    int beg = 1;

    for (int i = 1; i < n; i ++)
    {
        c[i] = cs[i];
        if (c[i] == '0')
        {
            update_interval(interval(beg, i, -1), 0);
            beg = i + 1;
        }
    }
    update_interval(interval(beg, n, -1), 0);
    ///cout << "--------------" << endl;
    for (int i = 1; i <= q; i ++)
    {
        if (base_ask[i].type == "toggle")
        {
            ///cout << "toggle" << endl;
            int pos = base_ask[i].x;
            if (c[pos] == '0')
            {
                c[pos] = '1';
                interval bef = bef1[i];
                interval aft = aft1[i];
                interval cur = cur1[i];
                update_interval(bef, i);
                update_interval(aft, i);
                update_interval(cur, i);
            }
            else
            {
                c[pos] = '0';
                ///set < interval > :: iterator cur_it = prev(st.lower_bound(interval(pos + 1, pos + 1, -1)));
                interval cur = cur1[i];
                interval bef = bef1[i];
                interval aft = aft1[i];

                update_interval(bef, i);
                update_interval(aft, i);
                update_interval(cur, i);

            }
        }
        else
        {
            int ans = query(base_ask[i].a, base_ask[i].b);

            cout << ans + add_ans[i] << endl;
        }

    }

    //for (pair < int, int > cur : available)
    //  cout << cur.first << " : " << cur.second << endl;
}
void solve()
{
    input();
    create_intervals();
    build_trees();
    simulate();

}

int main()
{
    solve();
    return 0;
}

Compilation message

street_lamps.cpp: In member function 'void BIT::add(int, int, int)':
street_lamps.cpp:54:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for (int j = y2; j < bit[i].size(); j += (j & -j))
      |                              ~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 90636 KB Output is correct
2 Correct 73 ms 90648 KB Output is correct
3 Correct 67 ms 90616 KB Output is correct
4 Correct 68 ms 90664 KB Output is correct
5 Correct 70 ms 90740 KB Output is correct
6 Correct 70 ms 90732 KB Output is correct
7 Correct 68 ms 90708 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 93116 KB Output is correct
2 Correct 454 ms 93516 KB Output is correct
3 Correct 718 ms 99588 KB Output is correct
4 Correct 1574 ms 164024 KB Output is correct
5 Correct 1379 ms 150776 KB Output is correct
6 Correct 1720 ms 169232 KB Output is correct
7 Correct 735 ms 106144 KB Output is correct
8 Correct 447 ms 94436 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 90952 KB Output is correct
2 Correct 78 ms 90956 KB Output is correct
3 Correct 70 ms 90908 KB Output is correct
4 Correct 68 ms 90700 KB Output is correct
5 Correct 1987 ms 193040 KB Output is correct
6 Correct 1808 ms 180916 KB Output is correct
7 Correct 1323 ms 154320 KB Output is correct
8 Correct 421 ms 100352 KB Output is correct
9 Correct 235 ms 95252 KB Output is correct
10 Correct 244 ms 95704 KB Output is correct
11 Correct 253 ms 95864 KB Output is correct
12 Correct 733 ms 111904 KB Output is correct
13 Correct 419 ms 100308 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 90828 KB Output is correct
2 Correct 71 ms 90912 KB Output is correct
3 Correct 71 ms 91080 KB Output is correct
4 Correct 70 ms 91032 KB Output is correct
5 Correct 830 ms 126108 KB Output is correct
6 Correct 1236 ms 149416 KB Output is correct
7 Correct 1616 ms 168500 KB Output is correct
8 Correct 2094 ms 191648 KB Output is correct
9 Correct 488 ms 95464 KB Output is correct
10 Correct 425 ms 93900 KB Output is correct
11 Correct 487 ms 95452 KB Output is correct
12 Correct 425 ms 93888 KB Output is correct
13 Correct 484 ms 95460 KB Output is correct
14 Correct 438 ms 94056 KB Output is correct
15 Correct 736 ms 111964 KB Output is correct
16 Correct 410 ms 100348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 90636 KB Output is correct
2 Correct 73 ms 90648 KB Output is correct
3 Correct 67 ms 90616 KB Output is correct
4 Correct 68 ms 90664 KB Output is correct
5 Correct 70 ms 90740 KB Output is correct
6 Correct 70 ms 90732 KB Output is correct
7 Correct 68 ms 90708 KB Output is correct
8 Correct 374 ms 93116 KB Output is correct
9 Correct 454 ms 93516 KB Output is correct
10 Correct 718 ms 99588 KB Output is correct
11 Correct 1574 ms 164024 KB Output is correct
12 Correct 1379 ms 150776 KB Output is correct
13 Correct 1720 ms 169232 KB Output is correct
14 Correct 735 ms 106144 KB Output is correct
15 Correct 447 ms 94436 KB Output is correct
16 Correct 75 ms 90952 KB Output is correct
17 Correct 78 ms 90956 KB Output is correct
18 Correct 70 ms 90908 KB Output is correct
19 Correct 68 ms 90700 KB Output is correct
20 Correct 1987 ms 193040 KB Output is correct
21 Correct 1808 ms 180916 KB Output is correct
22 Correct 1323 ms 154320 KB Output is correct
23 Correct 421 ms 100352 KB Output is correct
24 Correct 235 ms 95252 KB Output is correct
25 Correct 244 ms 95704 KB Output is correct
26 Correct 253 ms 95864 KB Output is correct
27 Correct 733 ms 111904 KB Output is correct
28 Correct 419 ms 100308 KB Output is correct
29 Correct 72 ms 90828 KB Output is correct
30 Correct 71 ms 90912 KB Output is correct
31 Correct 71 ms 91080 KB Output is correct
32 Correct 70 ms 91032 KB Output is correct
33 Correct 830 ms 126108 KB Output is correct
34 Correct 1236 ms 149416 KB Output is correct
35 Correct 1616 ms 168500 KB Output is correct
36 Correct 2094 ms 191648 KB Output is correct
37 Correct 488 ms 95464 KB Output is correct
38 Correct 425 ms 93900 KB Output is correct
39 Correct 487 ms 95452 KB Output is correct
40 Correct 425 ms 93888 KB Output is correct
41 Correct 484 ms 95460 KB Output is correct
42 Correct 438 ms 94056 KB Output is correct
43 Correct 736 ms 111964 KB Output is correct
44 Correct 410 ms 100348 KB Output is correct
45 Correct 236 ms 93804 KB Output is correct
46 Correct 274 ms 94072 KB Output is correct
47 Correct 823 ms 128432 KB Output is correct
48 Correct 1521 ms 167716 KB Output is correct
49 Correct 267 ms 95964 KB Output is correct
50 Correct 259 ms 95968 KB Output is correct
51 Correct 272 ms 96104 KB Output is correct
52 Correct 287 ms 96284 KB Output is correct
53 Correct 286 ms 96076 KB Output is correct
54 Correct 282 ms 96344 KB Output is correct