제출 #551601

#제출 시각아이디문제언어결과실행 시간메모리
551601Jarif_Rahman가로등 (APIO19_street_lamps)C++17
0 / 100
5042 ms10128 KiB
#include <bits/stdc++.h> #define pb push_back #define f first #define sc second using namespace std; typedef long long int ll; typedef string str; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; str s; cin >> s; set<tuple<int, int, int>> segments; vector<tuple<int, int, int>> old_segments; int ls = 0; for(int i = 0; i < n; i++){ if(s[i] == '0'){ if(ls < i) segments.insert({ls, i-1, 0}); ls = i+1; } } if(ls != n) segments.insert({ls, n-1, 0}); for(int qq = 1; qq <= q; qq++){ str tt; cin >> tt; if(tt == "toggle"){ int i; cin >> i; i--; if(s[i] == '0'){ auto it = segments.lower_bound(make_tuple(i, 0, 0)); if(it != segments.end() && get<0>(*it) == i+1 && it != segments.begin() && get<1>(*prev(it)) == i-1){ auto [l, r0, t1] = *prev(it); auto [l0, r, t2] = *it; it = segments.erase(prev(it)); segments.erase(it); old_segments.pb({l, r0, qq-t1}); old_segments.pb({l0, r, qq-t2}); segments.insert({l, r, qq}); } else if(it != segments.end() && get<0>(*it) == i+1){ auto [l, r, t] = *it; segments.erase(it); old_segments.pb({l, r, qq-t}); segments.insert({l-1, r, qq}); } else if(it != segments.begin() && get<1>(*prev(it)) == i-1){ it = prev(it); auto [l, r, t] = *it; segments.erase(it); old_segments.pb({l, r, qq-t}); segments.insert({l, r+1, qq}); } else segments.insert({i, i, qq}); s[i] = '1'; } else{ auto it = segments.upper_bound(make_tuple(i, -1, -1)); it--; auto [l, r, t] = *it; segments.erase(it); old_segments.pb({l, r, qq-t}); if(l != i) segments.insert({l, i-1, qq}); if(r != i) segments.insert({i+1, r, qq}); } } else{ int a, b; cin >> a >> b; a--, b-=2; int ans = 0; for(auto [l, r, t]: old_segments) if(l <= a && r >= b) ans+=t; for(auto [l, r, t]: segments) if(l <= a && r >= b) ans+=qq-t; cout << ans << "\n"; } } }
#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...