Submission #699142

#TimeUsernameProblemLanguageResultExecution timeMemory
699142puppyStreet Lamps (APIO19_street_lamps)C++17
100 / 100
4876 ms124880 KiB
#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 (stderr)

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;
      |             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...