제출 #729750

#제출 시각아이디문제언어결과실행 시간메모리
729750danikoynov가로등 (APIO19_street_lamps)C++14
20 / 100
1252 ms35568 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } struct interval { int left, right, in_time; interval(int _left, int _right, int _in_time) { left = _left; right = _right; in_time = _in_time; } bool operator < (const interval &it) const { return left < it.left; } }; const int maxn = 3e5 + 10; struct base_query { string type; int x, a, b; } base_ask[maxn]; int n, q; char c[maxn], cs[maxn]; void input() { cin >> n >> q; n ++; for (int i = 1; i < n; i ++) cin >> c[i], cs[i] = c[i]; for (int i = 1; i <= q; i ++) { cin >> base_ask[i].type; if (base_ask[i].type == "query") { cin >> base_ask[i].a >> base_ask[i].b; } else { cin >> base_ask[i].x; } } } set < pair < int, int > > available; void create_intervals() { set < interval > st; int beg = 1; for (int i = 1; i < n; i ++) { if (c[i] == '0') { ///cout << beg << " -- " << i << endl; st.insert(interval(beg, i, 0)); available.insert({beg, i}); beg = i + 1; } } st.insert(interval(beg, n, 0)); available.insert({beg, n}); for (int i = 1; i <= q; i ++) { if (base_ask[i].type == "toggle") { int pos = base_ask[i].x; if (c[pos] == '0') { c[pos] = '1'; set < interval > :: iterator aft_it = st.lower_bound(interval(pos + 1, pos + 1, -1)); set < interval > :: iterator bef_it = prev(aft_it); interval bef = *bef_it; interval aft = *aft_it; interval cur(bef.left, aft.right, i); st.erase(bef); st.erase(aft); st.insert(cur); available.insert({cur.left, cur.right}); } else { c[pos] = '0'; set < interval > :: iterator cur_it = prev(st.lower_bound(interval(pos + 1, pos + 1, -1))); interval cur = *cur_it; interval bef(cur.left, pos, i); interval aft(pos, cur.right, i); st.erase(cur); st.insert(bef); st.insert(aft); available.insert({bef.left, bef.right}); available.insert({aft.left, aft.right}); } } } //for (pair < int, int > cur : available) // cout << cur.first << " : " << cur.second << endl; } const int smalln = 110; int act[smalln][smalln], act_time[smalln][smalln], sum[smalln][smalln]; void update_interval(interval cur, int cur_time) { ///cout << "update " << cur.left << " " << cur.right << endl; if (act[cur.left][cur.right]) { act[cur.left][cur.right] = 0; sum[cur.left][cur.right] += cur_time - act_time[cur.left][cur.right]; } else { act_time[cur.left][cur.right] = cur_time; act[cur.left][cur.right] = 1; } } void simulate() { set < interval > st; int beg = 1; for (int i = 1; i < n; i ++) { c[i] = cs[i]; if (c[i] == '0') { st.insert(interval(beg, i, 0)); act[beg][i] = 1; act_time[beg][i] = 0; beg = i + 1; } } act[beg][n] = 1; st.insert(interval(beg, n, 0)); for (int i = 1; i <= q; i ++) { if (base_ask[i].type == "toggle") { ///cout << "toggle" << endl; int pos = base_ask[i].x; if (c[pos] == '0') { c[pos] = '1'; set < interval > :: iterator aft_it = st.lower_bound(interval(pos + 1, pos + 1, -1)); set < interval > :: iterator bef_it = prev(aft_it); interval bef = *bef_it; interval aft = *aft_it; interval cur(bef.left, aft.right, i); update_interval(bef, i); update_interval(aft, i); update_interval(cur, i); st.erase(bef); st.erase(aft); st.insert(cur); available.insert({cur.left, cur.right}); } else { c[pos] = '0'; set < interval > :: iterator cur_it = prev(st.lower_bound(interval(pos + 1, pos + 1, -1))); interval cur = *cur_it; interval bef(cur.left, pos, i); interval aft(pos + 1, cur.right, i); ///cout << " ::: " << bef.left << " " << bef.right << endl; st.erase(cur); st.insert(bef); st.insert(aft); update_interval(bef, i); update_interval(aft, i); update_interval(cur, i); available.insert({bef.left, bef.right}); available.insert({aft.left, aft.right}); } } else { ll ans = 0; for (int l = 1; l <= base_ask[i].a; l ++) for (int r = base_ask[i].b; r <= n; r ++) { ans = ans + sum[l][r]; ///cout << l << " -- " << r << " " << act[l][r] << endl; if (act[l][r]) { ///cout << l << " " << r << endl; ans = ans + i - act_time[l][r]; } } cout << ans << endl; } } //for (pair < int, int > cur : available) // cout << cur.first << " : " << cur.second << endl; } void solve() { input(); create_intervals(); simulate(); } int main() { solve(); return 0; } /** 5 3 11011 toggle 2 toggle 1 query 1 2 */
#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...