oj.uz

Submission #677875

# Submission time Handle Problem Language Result Execution time Memory
677875 2023-01-04T13:55:40 Z Tien_Noob Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1002 ms 103656 KB 
//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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 66004 KB Output is correct
2 Correct 32 ms 65972 KB Output is correct
3 Correct 37 ms 66004 KB Output is correct
4 Correct 39 ms 66092 KB Output is correct
5 Correct 32 ms 66056 KB Output is correct
6 Correct 32 ms 66080 KB Output is correct
7 Correct 32 ms 66004 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 74352 KB Output is correct
2 Correct 260 ms 74832 KB Output is correct
3 Correct 337 ms 75824 KB Output is correct
4 Correct 753 ms 100228 KB Output is correct
5 Correct 807 ms 101208 KB Output is correct
6 Correct 762 ms 100344 KB Output is correct
7 Correct 224 ms 75432 KB Output is correct
8 Correct 260 ms 76992 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 66232 KB Output is correct
2 Correct 32 ms 66208 KB Output is correct
3 Correct 32 ms 66192 KB Output is correct
4 Correct 32 ms 66088 KB Output is correct
5 Correct 984 ms 100508 KB Output is correct
6 Correct 929 ms 103656 KB Output is correct
7 Correct 769 ms 100736 KB Output is correct
8 Correct 232 ms 77004 KB Output is correct
9 Correct 121 ms 71804 KB Output is correct
10 Correct 120 ms 72052 KB Output is correct
11 Correct 117 ms 72368 KB Output is correct
12 Correct 227 ms 75468 KB Output is correct
13 Correct 222 ms 76836 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 66084 KB Output is correct
2 Correct 33 ms 66076 KB Output is correct
3 Correct 32 ms 66196 KB Output is correct
4 Correct 36 ms 66164 KB Output is correct
5 Correct 433 ms 94064 KB Output is correct
6 Correct 601 ms 97384 KB Output is correct
7 Correct 781 ms 99884 KB Output is correct
8 Correct 1002 ms 102328 KB Output is correct
9 Correct 288 ms 74460 KB Output is correct
10 Correct 270 ms 73656 KB Output is correct
11 Correct 274 ms 74476 KB Output is correct
12 Correct 259 ms 73644 KB Output is correct
13 Correct 262 ms 74444 KB Output is correct
14 Correct 295 ms 73704 KB Output is correct
15 Correct 225 ms 75476 KB Output is correct
16 Correct 244 ms 76844 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 66004 KB Output is correct
2 Correct 32 ms 65972 KB Output is correct
3 Correct 37 ms 66004 KB Output is correct
4 Correct 39 ms 66092 KB Output is correct
5 Correct 32 ms 66056 KB Output is correct
6 Correct 32 ms 66080 KB Output is correct
7 Correct 32 ms 66004 KB Output is correct
8 Correct 227 ms 74352 KB Output is correct
9 Correct 260 ms 74832 KB Output is correct
10 Correct 337 ms 75824 KB Output is correct
11 Correct 753 ms 100228 KB Output is correct
12 Correct 807 ms 101208 KB Output is correct
13 Correct 762 ms 100344 KB Output is correct
14 Correct 224 ms 75432 KB Output is correct
15 Correct 260 ms 76992 KB Output is correct
16 Correct 33 ms 66232 KB Output is correct
17 Correct 32 ms 66208 KB Output is correct
18 Correct 32 ms 66192 KB Output is correct
19 Correct 32 ms 66088 KB Output is correct
20 Correct 984 ms 100508 KB Output is correct
21 Correct 929 ms 103656 KB Output is correct
22 Correct 769 ms 100736 KB Output is correct
23 Correct 232 ms 77004 KB Output is correct
24 Correct 121 ms 71804 KB Output is correct
25 Correct 120 ms 72052 KB Output is correct
26 Correct 117 ms 72368 KB Output is correct
27 Correct 227 ms 75468 KB Output is correct
28 Correct 222 ms 76836 KB Output is correct
29 Correct 30 ms 66084 KB Output is correct
30 Correct 33 ms 66076 KB Output is correct
31 Correct 32 ms 66196 KB Output is correct
32 Correct 36 ms 66164 KB Output is correct
33 Correct 433 ms 94064 KB Output is correct
34 Correct 601 ms 97384 KB Output is correct
35 Correct 781 ms 99884 KB Output is correct
36 Correct 1002 ms 102328 KB Output is correct
37 Correct 288 ms 74460 KB Output is correct
38 Correct 270 ms 73656 KB Output is correct
39 Correct 274 ms 74476 KB Output is correct
40 Correct 259 ms 73644 KB Output is correct
41 Correct 262 ms 74444 KB Output is correct
42 Correct 295 ms 73704 KB Output is correct
43 Correct 225 ms 75476 KB Output is correct
44 Correct 244 ms 76844 KB Output is correct
45 Correct 118 ms 71064 KB Output is correct
46 Correct 155 ms 71260 KB Output is correct
47 Correct 429 ms 81276 KB Output is correct
48 Correct 751 ms 99632 KB Output is correct
49 Correct 121 ms 72524 KB Output is correct
50 Correct 118 ms 72420 KB Output is correct
51 Correct 133 ms 72732 KB Output is correct
52 Correct 127 ms 72928 KB Output is correct
53 Correct 127 ms 73036 KB Output is correct
54 Correct 132 ms 72932 KB Output is correct