제출 #729750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
729750		danikoynov	가로등 (APIO19_street_lamps)	C++14	20 / 100	1252 ms	35568 KiB

street_lamps

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

struct interval
{
    int left, right, in_time;

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

    bool operator < (const interval &it) const
    {
        return left < it.left;
    }
};

const int maxn = 3e5 + 10;

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

int n, q;
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;
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);
                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, cur.right, i);
                st.erase(cur);
                st.insert(bef);
                st.insert(aft);
                available.insert({bef.left, bef.right});
                available.insert({aft.left, aft.right});
            }
        }

    }

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

const int smalln = 110;

int act[smalln][smalln], act_time[smalln][smalln], sum[smalln][smalln];

void update_interval(interval cur, int cur_time)
{
        ///cout << "update " << cur.left << " " << cur.right << endl;
    if (act[cur.left][cur.right])
    {
        act[cur.left][cur.right] = 0;
        sum[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 simulate()
{
    set < interval > st;
    int beg = 1;
    for (int i = 1; i < n; i ++)
    {
        c[i] = cs[i];
        if (c[i] == '0')
        {

            st.insert(interval(beg, i, 0));
            act[beg][i] = 1;
            act_time[beg][i] = 0;
            beg = i + 1;
        }
    }
    act[beg][n] = 1;
    st.insert(interval(beg, n, 0));


    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';
                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);
                update_interval(bef, i);
                update_interval(aft, i);
                update_interval(cur, i);
                st.erase(bef);
                st.erase(aft);
                st.insert(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);
                ///cout << " ::: " << bef.left << " " << bef.right << endl;
                st.erase(cur);
                st.insert(bef);
                st.insert(aft);
                update_interval(bef, i);
                update_interval(aft, i);
                update_interval(cur, i);
                available.insert({bef.left, bef.right});
                available.insert({aft.left, aft.right});
            }
        }
        else
        {
            ll ans = 0;
            for (int l = 1; l <= base_ask[i].a; l ++)
                for (int r = base_ask[i].b; r <= n; r ++)
            {
                ans = ans + sum[l][r];
                ///cout << l << " -- " << r << " " << act[l][r] << endl;
                if (act[l][r])
                {
                    ///cout << l << " " << r << endl;
                    ans = ans + i - act_time[l][r];
                }
            }
            cout << ans << endl;
        }

    }

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

}

int main()
{
    solve();
    return 0;
}
/**
5 3
11011
toggle 2
toggle 1
query 1 2

*/

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20