Submission #729914

#	Time	Username	Problem	Language	Result	Execution time	Memory
729914		danikoynov	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2094 ms	193040 KiB

street_lamps

/**
 ____ ____ ____ ____ ____ ____
||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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20