oj.uz

Submission #699140

# Submission time Handle Problem Language Result Execution time Memory
699140 2023-02-15T19:00:24 Z puppy Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 109672 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>> vc;
void open(int t, int i, bool upd)
{
    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});
    if (upd) {
        vc.push_back({{lft, i-1}, -(Q-t)});
        vc.push_back({{i+1, rht}, -(Q-t)});
        vc.push_back({{lft, rht}, (Q-t)});
    }
}
void close(int t, int i, bool upd)
{
    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});
    if (upd) {
        vc.push_back({{lft, rht}, -(Q-t)});
        vc.push_back({{lft, i-1}, Q-t});
        vc.push_back({{i+1, rht}, Q-t});
    }
}
int now_time;
void process(int goal)
{
    if (now_time < goal) {
        while (now_time < goal) {
            now_time++;
            if (!state[now_time].type) {
                bool _now = cur[state[now_time].i];
                if (!_now) open(now_time, state[now_time].i, false);
                else close(now_time, state[now_time].i, false);
            }
        }
    }
    else if (now_time > goal) {
        while (now_time > goal) {
            if (!state[now_time].type) {
                bool _now = cur[state[now_time].i];
                if (!_now) open(now_time, state[now_time].i, false);
                else close(now_time, state[now_time].i, false);
            }
            now_time--;
        }
    }
}
bool visited[300005];

void dnc(int s, int e)
{
    if (s == e) {
        return;
    }
    int m = s + e >> 1;
    dnc(s, m);
    process(s-1);
    for (int i = s; i <= m; i++) {
        if (state[i].type == false) {
            if (cur[state[i].i] == false) open(i, state[i].i, true);
            else close(i, state[i].i, true);
        }
        else if (!visited[i]) {
            visited[i] = true;
            last[i] = is_connected(state[i].a, state[i].b);
        }
    }
    now_time = m;
    vector<pair<int, pair<int, pii>>> need;
    for (auto &i:vc) {
        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);
    vc.clear();
    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;
        }
    }
    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:117:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |     int m = s + e >> 1;
      |             ~~^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3071 ms 60176 KB Output is correct
2 Correct 3031 ms 60168 KB Output is correct
3 Correct 2810 ms 60788 KB Output is correct
4 Correct 3053 ms 68092 KB Output is correct
5 Correct 2621 ms 62552 KB Output is correct
6 Correct 3878 ms 89448 KB Output is correct
7 Correct 299 ms 20200 KB Output is correct
8 Correct 297 ms 20340 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 692 KB Output is correct
2 Correct 7 ms 712 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Execution timed out 5086 ms 109672 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 8 ms 716 KB Output is correct
4 Correct 10 ms 708 KB Output is correct
5 Correct 477 ms 26336 KB Output is correct
6 Correct 2270 ms 78428 KB Output is correct
7 Correct 3772 ms 87492 KB Output is correct
8 Execution timed out 5069 ms 105496 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3071 ms 60176 KB Output is correct
9 Correct 3031 ms 60168 KB Output is correct
10 Correct 2810 ms 60788 KB Output is correct
11 Correct 3053 ms 68092 KB Output is correct
12 Correct 2621 ms 62552 KB Output is correct
13 Correct 3878 ms 89448 KB Output is correct
14 Correct 299 ms 20200 KB Output is correct
15 Correct 297 ms 20340 KB Output is correct
16 Correct 11 ms 692 KB Output is correct
17 Correct 7 ms 712 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Execution timed out 5086 ms 109672 KB Time limit exceeded
21 Halted 0 ms 0 KB -