Submission #729888

# Submission time Handle Problem Language Result Execution time Memory
729888 2023-04-24T18:51:25 Z danikoynov Street Lamps (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, 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];



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)
{
    if (tree[root].size() < 20)
    {
        int lf = 0;
        while(lf < tree[root].size() && tree[root][lf].second < cur.second)
            lf ++;
        while(lf < tree[root].size() && tree[root][lf].second == cur.second && tree[root][lf].first < cur.first)
        lf ++;
        return lf;
    }
    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

*/

Compilation message

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 'int lower_bound_simulate(int, std::pair<int, int>)':
street_lamps.cpp:180:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |         while(lf < tree[root].size() && tree[root][lf].second < cur.second)
      |               ~~~^~~~~~~~~~~~~~~~~~~
street_lamps.cpp:182:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |         while(lf < tree[root].size() && tree[root][lf].second == cur.second && tree[root][lf].first < cur.first)
      |               ~~~^~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void conquer(int, int, int)':
street_lamps.cpp:293: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]
  293 |     while(left < tree[lf].size() && right < tree[rf].size())
      |           ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:293: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]
  293 |     while(left < tree[lf].size() && right < tree[rf].size())
      |                                     ~~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:313: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]
  313 |     while(left < tree[lf].size())
      |           ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:316: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]
  316 |     while(right < tree[rf].size())
      |           ~~~~~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 98 ms 205772 KB Output is correct
2 Correct 95 ms 205696 KB Output is correct
3 Correct 97 ms 205716 KB Output is correct
4 Correct 100 ms 205772 KB Output is correct
5 Correct 97 ms 205840 KB Output is correct
6 Correct 95 ms 205828 KB Output is correct
7 Correct 100 ms 205836 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 654 ms 207264 KB Output is correct
2 Correct 843 ms 207944 KB Output is correct
3 Correct 1809 ms 223616 KB Output is correct
4 Correct 4601 ms 489136 KB Output is correct
5 Correct 3700 ms 414652 KB Output is correct
6 Execution timed out 5100 ms 505392 KB Time limit exceeded
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 108 ms 206788 KB Output is correct
2 Correct 104 ms 206652 KB Output is correct
3 Correct 103 ms 206288 KB Output is correct
4 Correct 99 ms 205936 KB Output is correct
5 Runtime error 1062 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 104 ms 206340 KB Output is correct
2 Correct 100 ms 206428 KB Output is correct
3 Correct 102 ms 206520 KB Output is correct
4 Correct 105 ms 206620 KB Output is correct
5 Correct 1326 ms 382956 KB Output is correct
6 Correct 3270 ms 449880 KB Output is correct
7 Execution timed out 5109 ms 505052 KB Time limit exceeded
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 98 ms 205772 KB Output is correct
2 Correct 95 ms 205696 KB Output is correct
3 Correct 97 ms 205716 KB Output is correct
4 Correct 100 ms 205772 KB Output is correct
5 Correct 97 ms 205840 KB Output is correct
6 Correct 95 ms 205828 KB Output is correct
7 Correct 100 ms 205836 KB Output is correct
8 Correct 654 ms 207264 KB Output is correct
9 Correct 843 ms 207944 KB Output is correct
10 Correct 1809 ms 223616 KB Output is correct
11 Correct 4601 ms 489136 KB Output is correct
12 Correct 3700 ms 414652 KB Output is correct
13 Execution timed out 5100 ms 505392 KB Time limit exceeded
14 Halted 0 ms 0 KB -