제출 #699140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699140		puppy	가로등 (APIO19_street_lamps)	C++17	40 / 100	5086 ms	109672 KiB

street_lamps

#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';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20