제출 #729873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
729873		danikoynov	가로등 (APIO19_street_lamps)	C++14	20 / 100	5101 ms	524288 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 = 0, int _right = 0, int _in_time = 0)
    {
        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];

struct fenwick
{
    vector < int > fen;
    int n, full = 0;
    fenwick() {};

    fenwick(int _n)
    {
        n = _n;
        fen.resize(n + 1);
    }

    void update(int v, int val)
    {
        v ++;
        if (v > 0 && v <= n)
            full += val;
        for (int i = v; i <= n; i += (i&-i))
            fen[i] += val;
    }

    int sum(int v)
    {
        v ++;
        int s = 0;
        for (int i = v; i > 0; i -= (i&-i))
            s += fen[i];
        return s;
    }

    int query(int left, int right)
    {
        if (left > right)
            return 0;
            if (left != right)
                return full - sum(left - 1);
        return sum(right) - sum(left - 1);
    }
};

fenwick f[maxn * 4][3];
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});
            }
        }

    }

    //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];

struct node
{
    int act_cnt, sum_act;

    node(int _act_cnt = 0, int _sum_act = 0)
    {
        act_cnt = _act_cnt;
        sum_act = _sum_act;
    }
};

node merge_node(node bef, node aft)
{
    node cur;
    cur.act_cnt = bef.act_cnt + aft.act_cnt;

    cur.sum_act = bef.sum_act + aft.sum_act;
    return cur;
}


vector < pair < int, int > > tree[4 * maxn], values[maxn];
unordered_map < int, int > act_time[maxn], act[maxn];
int lower_bound_simulate(int root, pair < int, int > cur)
{
    int lf = 0, rf = (int)(tree[root].size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (tree[root][mf].second < cur.second)
            lf = mf + 1;
        else if (tree[root][mf].second > cur.second)
            rf = mf - 1;
        else
        {
            if (tree[root][mf].first < cur.first)
                lf = mf + 1;
            else
                rf = mf - 1;
        }
    }
    return lf;
}
void toggle_node(int root, pair < int, int > &cur, int &cur_time)
{
    int lf = lower_bound_simulate(root, cur);


    if (act[cur.first][cur.second] == 0)
    {
        f[root][1].update(lf, -1);
        ///cout << "toggle " << root << " " << cur.first << " " << cur.second << endl;
        f[root][0].update(lf, cur_time - act_time[cur.first][cur.second]);

        int val = - f[root][2].query(lf, lf);
        f[root][2].update(lf, val);
    }
    else
    {
        f[root][1].update(lf, 1);
        int val = cur_time - f[root][2].query(lf, lf);
        f[root][2].update(lf, val);
    }


}
void toggle(int root, int left, int right, pair < int, int > cur, int &cur_time)
{
    while(true)
    {

        toggle_node(root, cur, cur_time);
        if (left == right)
            break;

        int mid = (left + right) / 2;
        if (cur.first <= mid)
        {
            root *= 2;
            right = mid;
        }
        else
        {
            root = root * 2 + 1;
            left = mid + 1;
        }
    }
}

void update_interval(interval cur, int cur_time)
{
    if (act[cur.left][cur.right] == 0)
    {
        act[cur.left][cur.right] = 1;
    }
    else
    {
        act[cur.left][cur.right] = 0;
    }
    ///if (available.find({cur.left, cur.right}) == available.end())
    /// while(true);
    ///cout << "update " << cur.left << " " << cur.right << endl;
    toggle(1, 1, n, {cur.left, cur.right}, cur_time);

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


int query(int root, int left, int right, pair < int, int > val, int cur_time)
{
    if (left > val.first)
        return 0;
    if (right <= val.first)
    {
        ///cout << root << " : " << left << " : " << right << " : " << val.first << " : " << val.second << endl;
        int lf = lower_bound_simulate(root, {-1, val.second}), ans;

        ans = f[root][1].query(lf, (int)(tree[root].size()) - 1) * cur_time - f[root][2].query(lf, (int)(tree[root].size()) - 1) + f[root][0].query(lf, (int)(tree[root].size()) - 1);

        return ans;
    }

    int mid = (left + right) / 2;
    return query(root * 2, left, mid, val, cur_time) +
           query(root * 2 + 1, mid + 1, right, val, cur_time);

}

void conquer(int root, int lf, int rf)
{
    int left = 0, right = 0;
    while(left < tree[lf].size() && right < tree[rf].size())
    {
        if (tree[lf][left].second < tree[rf][right].second)
        {
            tree[root].push_back(tree[lf][left ++]);
        }
        else if (tree[lf][left].second > tree[rf][right].second)
        {
            tree[root].push_back(tree[rf][right ++]);
        }
        else if (tree[lf][left].first < tree[rf][right].first)
        {
            tree[root].push_back(tree[lf][left ++]);
        }
        else
        {
            tree[root].push_back(tree[rf][right ++]);
        }
    }

    while(left < tree[lf].size())
        tree[root].push_back(tree[lf][left ++]);

    while(right < tree[rf].size())
        tree[root].push_back(tree[rf][right ++]);


    f[root][1] = fenwick(tree[root].size());
    f[root][0] = fenwick(tree[root].size());
    f[root][2] = fenwick(tree[root].size());
}

void divide(int root, int left, int right)
{
    if (left == right)
    {
        tree[root] = values[left];

        f[root][0] = fenwick(tree[root].size());
        f[root][1] = fenwick(tree[root].size());
        f[root][2] = fenwick(tree[root].size());
        return;
    }

    int mid = (left + right) / 2;
    divide(root * 2, left, mid);
    divide(root * 2 + 1, mid + 1, right);

    conquer(root, root * 2, root * 2 + 1);
}

void build_trees()
{
    for (pair < int, int > cur : available)
    {
        values[cur.first].push_back(cur);
    }

    divide(1, 1, n);
}
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(1, 1, n, {base_ask[i].a, base_ask[i].b}, i);

            cout << ans << endl;
        }

    }

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

}

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

*/

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In member function 'int fenwick::query(int, int)':
street_lamps.cpp:74:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   74 |         if (left > right)
      |         ^~
street_lamps.cpp:76:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   76 |             if (left != right)
      |             ^~
street_lamps.cpp: In function 'void conquer(int, int, int)':
street_lamps.cpp:303:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  303 |     while(left < tree[lf].size() && right < tree[rf].size())
      |           ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:303:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  303 |     while(left < tree[lf].size() && right < tree[rf].size())
      |                                     ~~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:323:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  323 |     while(left < tree[lf].size())
      |           ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:326:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  326 |     while(right < tree[rf].size())
      |           ~~~~~~^~~~~~~~~~~~~~~~~

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