답안 #729849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
729849 2023-04-24T18:05:15 Z danikoynov 가로등 (APIO19_street_lamps) C++14
20 / 100
5000 ms 524288 KB
#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;
    fenwick(){};

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

    void update(int v, int val)
    {
        v ++;
        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;
        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];
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)
{
    toggle_node(root, cur, cur_time);
    if (left == right)
        return;

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

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);
            /**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 << " " << act_time[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();
    build_trees();
    simulate();

}

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

*/

Compilation message

street_lamps.cpp: In function 'void conquer(int, int, int)':
street_lamps.cpp:289: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]
  289 |     while(left < tree[lf].size() && right < tree[rf].size())
      |           ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:289: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]
  289 |     while(left < tree[lf].size() && right < tree[rf].size())
      |                                     ~~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:309: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]
  309 |     while(left < tree[lf].size())
      |           ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:312: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]
  312 |     while(right < tree[rf].size())
      |           ~~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 201036 KB Output is correct
2 Correct 106 ms 201000 KB Output is correct
3 Correct 97 ms 201032 KB Output is correct
4 Correct 92 ms 201036 KB Output is correct
5 Correct 101 ms 201144 KB Output is correct
6 Correct 102 ms 201140 KB Output is correct
7 Correct 102 ms 201080 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 814 ms 202444 KB Output is correct
2 Correct 1018 ms 203284 KB Output is correct
3 Correct 2052 ms 218896 KB Output is correct
4 Correct 4638 ms 449024 KB Output is correct
5 Correct 3854 ms 396452 KB Output is correct
6 Execution timed out 5089 ms 469492 KB Time limit exceeded
7 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 202052 KB Output is correct
2 Correct 101 ms 201800 KB Output is correct
3 Correct 105 ms 201548 KB Output is correct
4 Correct 105 ms 201268 KB Output is correct
5 Runtime error 1237 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 201500 KB Output is correct
2 Correct 102 ms 201580 KB Output is correct
3 Correct 104 ms 201784 KB Output is correct
4 Correct 106 ms 201840 KB Output is correct
5 Correct 1303 ms 349960 KB Output is correct
6 Correct 3105 ms 417640 KB Output is correct
7 Execution timed out 5075 ms 464444 KB Time limit exceeded
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 201036 KB Output is correct
2 Correct 106 ms 201000 KB Output is correct
3 Correct 97 ms 201032 KB Output is correct
4 Correct 92 ms 201036 KB Output is correct
5 Correct 101 ms 201144 KB Output is correct
6 Correct 102 ms 201140 KB Output is correct
7 Correct 102 ms 201080 KB Output is correct
8 Correct 814 ms 202444 KB Output is correct
9 Correct 1018 ms 203284 KB Output is correct
10 Correct 2052 ms 218896 KB Output is correct
11 Correct 4638 ms 449024 KB Output is correct
12 Correct 3854 ms 396452 KB Output is correct
13 Execution timed out 5089 ms 469492 KB Time limit exceeded
14 Halted 0 ms 0 KB -