oj.uz

Submission #699142

# Submission time Handle Problem Language Result Execution time Memory
699142 2023-02-15T19:11:44 Z puppy Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4876 ms 124880 KB 
#pragma GCC optimize("O3")
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;
int ans[300005];
bool last[300005];
struct State
{
    bool type; //0:update, 1:query
    int i, a, b;
};
int N, Q;
State state[300005];
bool cur[300005];
set<pii> st;
const int sz = 1 << 19;
int tree[1<<19];
void upd(int id, int v)
{
    for (int i = id; i < sz; i += i&-i) {
        tree[i] += v;
    }
}
int query(int id)
{
    int ret = 0;
    for (int i = id; i; i -= i&-i) {
        ret += tree[i];
    }
    return ret;
}
bool is_connected(int a, int b)
{
    if (st.empty()) return false;
    auto it = st.lower_bound({a+1, 0});
    if (it == st.begin()) return false;
    --it;
    return b <= (*it).second;
}
vector<pair<pii, int>> lst[300005];
void open(int t, int i)
{
    cur[i] = true;
    auto it = st.lower_bound({i+1, 0});
    auto it2 = it;
    int lft = -1, rht = -1;
    if (it == st.end() || (*it).first != i+1) rht = i;
    else rht = (*it).second;
    if (it == st.begin()) lft = i;
    else {
        --it;
        if ((*it).second != i-1) lft = i;
        else lft = (*it).first;
    }
    auto it3 = it2;
    if (it3 != st.begin()) {
        --it3;
        if ((*it3).second == i-1) st.erase(it3);
    }
    if (it2 != st.end() && (*it2).first == i+1) st.erase(it2);
    st.insert({lft, rht});
    lst[t].push_back({{lft, i-1}, -(Q-t)});
    lst[t].push_back({{i+1, rht}, -(Q-t)});
    lst[t].push_back({{lft, rht}, (Q-t)});
}
void close(int t, int i)
{
    cur[i] = false;
    auto it = st.lower_bound({i+1, 0});
    --it;
    int lft = (*it).first, rht = (*it).second;
    st.erase(it);
    if (lft <= i-1) st.insert({lft, i-1});
    if (i+1 <= rht) st.insert({i+1, rht});
    lst[t].push_back({{lft, rht}, -(Q-t)});
    lst[t].push_back({{lft, i-1}, Q-t});
    lst[t].push_back({{i+1, rht}, Q-t});
}
void dnc(int s, int e)
{
    if (s == e) return;
    vector<pair<int, pair<int, pii>>> need;
    int m = s + e >> 1;
    for (int k = s; k <= m; k++) {
        for (auto &i:lst[k]) {
            need.push_back({i.first.first, {0, {i.first.first, i.second}}});
            need.push_back({i.first.first, {0, {i.first.second+1, -i.second}}});
            need.push_back({i.first.second+1, {0, {i.first.first, -i.second}}});
            need.push_back({i.first.second+1, {0, {i.first.second+1, i.second}}});
        }
    }
    for (int i = m+1; i <= e; i++) {
        if (state[i].type == true) {
            need.push_back({state[i].a, {1, {state[i].b, i}}});
        }
    }
    sort(need.begin(), need.end());
    vector<pair<int, int>> tag;
    for (auto &k:need) {
        if (k.second.first == 0) {
            upd(k.second.second.first, k.second.second.second);
            tag.push_back({k.second.second.first, k.second.second.second});
        }
        else {
            ans[k.second.second.second] += query(k.second.second.first);
        }
    }
    for (pair<int, int> &p:tag) upd(p.first, -p.second);
    dnc(s, m);
    dnc(m+1, e);
}
int lst_cnt[300005];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> Q;
    string s; cin >> s;
    for (int i = 1; i <= N; i++) cur[i] = (s[i-1] - '0');
    for (int i = 1; i <= N; i++) {
        if (!cur[i]) {
            lst_cnt[i] = -1;
            continue;
        }
        int s = i;
        while (i + 1 <= N && cur[i+1]) ++i;
        int e = i;
        for (int k = s; k <= e; k++) lst_cnt[k] = e;
        st.insert({s, e});
    }
    for (int i = 1; i <= Q; i++) {
        string s; cin >> s;
        if (s == "toggle") {
            int k; cin >> k;
            state[i].type = false;
            state[i].i = k;
        }
        else {
            int a, b; cin >> a >> b; b--;
            state[i].type = true;
            state[i].a = a, state[i].b = b;
            if (b <= lst_cnt[a]) ans[i] = Q;
        }
    }
    for (int i = 1; i <= Q; i++) {
        if (!state[i].type) {
            if (!cur[state[i].i]) open(i, state[i].i);
            else close(i, state[i].i);
        }
        else last[i] = is_connected(state[i].a, state[i].b);
    }
    dnc(1, Q);
    for (int i = 1; i <= Q; i++) {
        if (!state[i].type) continue;
        if (last[i]) ans[i] -= (Q - i);
        cout << ans[i] << '\n';
    }
}

Compilation message

street_lamps.cpp: In function 'void dnc(int, int)':
street_lamps.cpp:86:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     int m = s + e >> 1;
      |             ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2670 ms 69048 KB Output is correct
2 Correct 2677 ms 69468 KB Output is correct
3 Correct 2281 ms 69000 KB Output is correct
4 Correct 2148 ms 76460 KB Output is correct
5 Correct 1783 ms 63928 KB Output is correct
6 Correct 2597 ms 121004 KB Output is correct
7 Correct 313 ms 20812 KB Output is correct
8 Correct 303 ms 20868 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7944 KB Output is correct
2 Correct 10 ms 7764 KB Output is correct
3 Correct 9 ms 7636 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 3613 ms 124880 KB Output is correct
6 Correct 2762 ms 115136 KB Output is correct
7 Correct 1767 ms 69392 KB Output is correct
8 Correct 319 ms 26804 KB Output is correct
9 Correct 188 ms 19592 KB Output is correct
10 Correct 214 ms 21716 KB Output is correct
11 Correct 223 ms 21748 KB Output is correct
12 Correct 321 ms 26788 KB Output is correct
13 Correct 330 ms 26736 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7508 KB Output is correct
2 Correct 8 ms 7764 KB Output is correct
3 Correct 10 ms 7752 KB Output is correct
4 Correct 11 ms 7796 KB Output is correct
5 Correct 444 ms 32864 KB Output is correct
6 Correct 1552 ms 99560 KB Output is correct
7 Correct 2508 ms 121032 KB Output is correct
8 Correct 3647 ms 124480 KB Output is correct
9 Correct 3671 ms 118352 KB Output is correct
10 Correct 4841 ms 120860 KB Output is correct
11 Correct 3685 ms 118340 KB Output is correct
12 Correct 4832 ms 120856 KB Output is correct
13 Correct 3792 ms 118296 KB Output is correct
14 Correct 4876 ms 120804 KB Output is correct
15 Correct 316 ms 26824 KB Output is correct
16 Correct 298 ms 26764 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 2670 ms 69048 KB Output is correct
9 Correct 2677 ms 69468 KB Output is correct
10 Correct 2281 ms 69000 KB Output is correct
11 Correct 2148 ms 76460 KB Output is correct
12 Correct 1783 ms 63928 KB Output is correct
13 Correct 2597 ms 121004 KB Output is correct
14 Correct 313 ms 20812 KB Output is correct
15 Correct 303 ms 20868 KB Output is correct
16 Correct 16 ms 7944 KB Output is correct
17 Correct 10 ms 7764 KB Output is correct
18 Correct 9 ms 7636 KB Output is correct
19 Correct 5 ms 7380 KB Output is correct
20 Correct 3613 ms 124880 KB Output is correct
21 Correct 2762 ms 115136 KB Output is correct
22 Correct 1767 ms 69392 KB Output is correct
23 Correct 319 ms 26804 KB Output is correct
24 Correct 188 ms 19592 KB Output is correct
25 Correct 214 ms 21716 KB Output is correct
26 Correct 223 ms 21748 KB Output is correct
27 Correct 321 ms 26788 KB Output is correct
28 Correct 330 ms 26736 KB Output is correct
29 Correct 5 ms 7508 KB Output is correct
30 Correct 8 ms 7764 KB Output is correct
31 Correct 10 ms 7752 KB Output is correct
32 Correct 11 ms 7796 KB Output is correct
33 Correct 444 ms 32864 KB Output is correct
34 Correct 1552 ms 99560 KB Output is correct
35 Correct 2508 ms 121032 KB Output is correct
36 Correct 3647 ms 124480 KB Output is correct
37 Correct 3671 ms 118352 KB Output is correct
38 Correct 4841 ms 120860 KB Output is correct
39 Correct 3685 ms 118340 KB Output is correct
40 Correct 4832 ms 120856 KB Output is correct
41 Correct 3792 ms 118296 KB Output is correct
42 Correct 4876 ms 120804 KB Output is correct
43 Correct 316 ms 26824 KB Output is correct
44 Correct 298 ms 26764 KB Output is correct
45 Correct 1863 ms 53196 KB Output is correct
46 Correct 1704 ms 56488 KB Output is correct
47 Correct 1408 ms 59412 KB Output is correct
48 Correct 2118 ms 81132 KB Output is correct
49 Correct 240 ms 23264 KB Output is correct
50 Correct 242 ms 23184 KB Output is correct
51 Correct 239 ms 23324 KB Output is correct
52 Correct 245 ms 23628 KB Output is correct
53 Correct 218 ms 23624 KB Output is correct
54 Correct 214 ms 23640 KB Output is correct