Submission #605254

#	Time	Username	Problem	Language	Result	Execution time	Memory
605254		IWannaHaveAGirlfriend	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1032 ms	102428 KiB

street_lamps

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 3e5 + 1;
struct SegmentTree
{
    struct FenwickTree
    {
        vector<int> tree;
        int sz;
        void Assign(int _sz)
        {
            sz = _sz;
            tree.resize(sz, 0);
        }
        void add(int pos, int val)
        {
            for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
            {
                tree[pos] += val;
            }
        }
        int sum(int pos)
        {
            int ret = 0;
            for (; pos < sz; pos |= pos + 1)
            {
                ret += tree[pos];
            }
            return ret;
        }
    } tree[4 * N + 1];
    vector<int> num[4 * N + 1];
    void add_num(int v, int TreeL, int TreeR, int L, int R, int val)
    {
        if (L > R)
        {
            return ;
        }
        if (TreeL == L && TreeR == R)
        {
            num[v].push_back(val);
            return ;
        }
        int mid = (TreeL + TreeR)/2;
        add_num(v * 2, TreeL, mid, L, min(R, mid), val);
        add_num(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R, val);
    }
    void build(int v, int TreeL, int TreeR)
    {
        sort(num[v].begin(), num[v].end());
        num[v].erase(unique(num[v].begin(), num[v].end()), num[v].end());
        tree[v].Assign(num[v].size());
        if (TreeL == TreeR)
        {
            return ;
        }
        int mid = (TreeL + TreeR)/2;
        build(v * 2, TreeL, mid);
        build(v * 2 + 1, mid + 1, TreeR);
    }
    int convert(int v, int x)
    {
        return lower_bound(num[v].begin(), num[v].end(), x) - num[v].begin();
    }
    void add_val(int v, int TreeL, int TreeR, int L, int R, int num, int val)
    {
        if (L > R)
        {
            return ;
        }
        if (TreeL == L && TreeR == R)
        {
            tree[v].add(convert(v, num), val);
            return ;
        }
        int mid = (TreeL + TreeR)/2;
        add_val(v * 2, TreeL, mid, L, min(R, mid), num, val);
        add_val(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R, num, val);
    }
    int get(int v, int TreeL, int TreeR, int pos, int fn)
    {
        int ret = tree[v].sum(convert(v, fn));
        if (TreeL == TreeR)
        {
            return ret;
        }
        int mid = (TreeL + TreeR)/2;
        if (pos <= mid)
        {
            return ret + get(v * 2, TreeL, mid, pos, fn);
        }
        else
        {
            return ret + get(v * 2 + 1, mid + 1, TreeR, pos, fn);
        }
    }
} tree;
char lamp[N + 1], st_lamp[N + 1];
int n, q, a[N + 1], b[N + 1];
set<tuple<int, int, int> > st_state, cur;
void read()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> st_lamp[i];
        lamp[i] = st_lamp[i];
    }
    int l = -1, r = -1;
    for (int i = 1; i <= n; ++ i)
    {
        if (lamp[i] == '0')
        {
            if (l != -1 && r != -1)
            {
                st_state.insert({l, r, 0});
                l = r = -1;
            }
        }
        else
        {
            if (l == -1)
            {
                l = i;
            }
            r = i + 1;
        }
    }
    if (l != -1 && r != -1)
    {
        st_state.insert({l, r, 0});
    }
    cur = st_state;
}
set<tuple<int, int, int> > :: iterator contain(int x)
{
    set<tuple<int, int, int> > :: iterator it = cur.upper_bound({x, N + 10, N + 10});
    if (it != cur.begin())
    {
        --it;
    }
    if (it == cur.end())
    {
        return it;
    }
    int l, r, t;
    tie(l, r, t) = *it;
    if (l <= x && x <= r)
    {
        return it;
    }
    else
    {
        return cur.end();
    }
}
void solve()
{
    for (auto &[l, r, t] : cur)
    {
        //cerr << l << ' ' << r << '\n';
        tree.add_num(1, 1, n + 1, l, r, r);
    }
    for (int i = 1; i <= q; ++ i)
    {
        string s;
        cin >> s;
        if (s == "query")
        {
            cin >> a[i] >> b[i];
        }
        else
        {
            cin >> a[i];
            if (lamp[a[i]] == '0')
            {
                lamp[a[i]] = '1';
                int l = a[i], r = a[i] + 1;
                auto it = contain(a[i] + 1);
                if (it != cur.end())
                {
                    r = get<1> (*it);
                    cur.erase(it);
                }
                it = contain(a[i]);
                if (it != cur.end())
                {
                    l = get<0> (*it);
                    cur.erase(it);
                }
                //cerr << l << ' ' << r << '\n';
                cur.insert({l, r, i});
                tree.add_num(1, 1, n + 1, l, r, r);
            }
            else
            {
                lamp[a[i]] = '0';
                auto it = contain(a[i]);
                int l = get<0> (*it), r = get<1> (*it);
                cur.erase(it);
                //cerr << l << ' ' << r << '\n';
                if (l < a[i])
                {
                    cur.insert({l, a[i], i});
                    tree.add_num(1, 1, n + 1, l, a[i], a[i]);
                }
                if (r > a[i] + 1)
                {
                    cur.insert({a[i] + 1, r, i});
                    tree.add_num(1, 1, n + 1, a[i] + 1, r, r);
                }
            }
        }
    }
    tree.build(1, 1, n + 1);
    cur = st_state;
    copy(st_lamp + 1, st_lamp + n + 1, lamp + 1);
    for (auto &[l, r, t] : cur)
    {
        //cerr << l << ' ' << r << '\n';
        //tree.add_val(1, 1, n + 1, l, r, r, 1);
    }
    for (int i = 1; i <= q; ++ i)
    {
        if (b[i]) // query
        {
            int res = tree.get(1, 1, n + 1, a[i], b[i]);
            auto it = contain(a[i]);
            if (it != cur.end() && get<1> (*it) >= b[i])
            {
                res += i - get<2> (*it);
            }
            cout << res << '\n';
        }
        else // update
        {
            if (lamp[a[i]] == '0')
            {
                lamp[a[i]] = '1';
                int l = a[i], r = a[i] + 1;
                auto it = contain(a[i] + 1);
                if (it != cur.end())
                {
                    r = get<1> (*it);
                    tree.add_val(1, 1, n + 1, a[i] + 1, r, r, i - get<2> (*it));
                    cur.erase(it);
                }
                it = contain(a[i]);
                if (it != cur.end())
                {
                    l = get<0> (*it);
                    tree.add_val(1, 1, n + 1, l, a[i], a[i], i - get<2> (*it));
                    cur.erase(it);
                }
                cur.insert({l, r, i});
            }
            else
            {
                lamp[a[i]] = '0';
                auto it = contain(a[i]);
                int l, r, t;
                tie(l, r, t) = *it;
                cur.erase(it);
                tree.add_val(1, 1, n + 1, l, r, r, i - t);
                if (l < a[i])
                {
                    cur.insert({l, a[i], i});
                    //tree.add_val(1, 1, n + 1, l, a[i], a[i], i - 1 - t);
                }
                if (r > a[i] + 1)
                {
                    cur.insert({a[i] + 1, r, i});
                    //tree.add_val(1, 1, n + 1, a[i] + 1, r, r, i - 1 - t);
                }
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:222:16: warning: unused structured binding declaration [-Wunused-variable]
  222 |     for (auto &[l, r, t] : cur)
      |                ^~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:289:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  289 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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