제출 #263050

#제출 시각아이디문제언어결과실행 시간메모리
263050Falcon가로등 (APIO19_street_lamps)C++14
0 / 100
408 ms25996 KiB
#pragma GCC optimize("O2") #include <bits/stdc++.h> #ifdef DEBUG #include "debug.hpp" #endif using namespace std; #define all(c) (c).begin(), (c).end() #define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++) #define rep(i, N) for(int i = 0; i < (N); i++) #define rep1(i, N) for(int i = 1; i <= (N); i++) #define rep2(i, s, e) for(int i = (s); i <= (e); i++) #define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d)) #define pb push_back #ifdef DEBUG #define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);} #define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << " " << #x << " = " << x << endl; dbg::light = 0;} #else #define debug(x...) #define light_debug(x) #endif template<typename T> T& ckmin(T& a, T b){ return a = a > b ? b : a; } template<typename T> T& ckmax(T& a, T b){ return a = a < b ? b : a; } using ll = long long; using pii = pair<int, int>; using vi = vector<int>; template<int n> struct BIT{ array<int, n + 1> a; vi modifications; void update(int i, int v){ for(i++; i <= n; i += i & -i) a[i] += v, modifications.pb(i); } int query(int i) const { int s = 0; for(i++; i; i -= i & -i) s += a[i]; return s; } void clear(){ for(int i : modifications) a[i] = 0; modifications.clear(); } }; struct interval{ int l, r, t; // [l, r) is one at time t; bool operator <(const interval& x) const{ return l < x.l; // Enough, because no two intervals can have the same left endpoint (disjoint intervals). } }; string to_string(interval x){ return "{" + to_string(x.l) + ", " + to_string(x.r) + ", " + to_string(x.t) + "}"; } struct offline_interval{ int l, r, t, d; }; vi is_query, ans; vector<offline_interval> a; BIT<300001> bit; void CDQ(int s, int e){ debug(s, e); if(e - s <= 1) return; int m = (s + e) >> 1; CDQ(s, m), CDQ(m, e); vector<offline_interval> tmp; tmp.reserve(e - s); for(int x = s, y = m; x < m || y < e;){ if(x < m && (y == e || a[x].l <= a[y].l)){ if(is_query[a[x].t]) bit.update(a[x].r, a[x].d); tmp.pb(a[x++]); }else{ if(is_query[a[y].t]) ans[a[y].t] += bit.query(a[y].r); tmp.pb(a[y++]); } } bit.clear(); rep2(i, s, e - 1) a[i] = tmp[i - s]; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); #ifdef DEBUG freopen("debug", "w", stderr); #endif int n, q; cin >> n >> q; string status; cin >> status; is_query.resize(q + 1), ans.resize(q + 1); set<interval> intervals; for(int i = 0; i < n;){ while(i < n && status[i] == '0') i++; int e = i; for(; e < n && status[e] == '1'; e++); if(e != i) intervals.insert({i, e, 0}); i = e; } auto toggle = [&](int i, int t){ auto next_ = intervals.upper_bound({i, -1, -1}); if(status[i] == '1'){ assert(next_ != intervals.begin()); auto cur = prev(next_); auto tmp = *cur; intervals.erase(cur); a.pb({tmp.l, tmp.r, t, t - tmp.t}); int l = tmp.l, r = tmp.r; if(l < i) intervals.insert({l, i, t}); if(r > i + 1) intervals.insert({i + 1, r, t}); status[i] = '0'; } else { interval itvl = {i, i + 1, t}; if(next_ != intervals.begin() && prev(next_)->r == i){ auto pre = prev(next_); itvl.l = pre->l; a.pb({pre->l, pre->r, pre->t, t - pre->t}); intervals.erase(pre); } if(next_ != intervals.end() && next_->l == i + 1){ itvl.r = next_->r; a.pb({next_->l, next_->r, next_->t, t - next_->t}); intervals.erase(next_); } intervals.insert(itvl); status[i] = '1'; } }; rep1(t, q){ string qtype; cin >> qtype; if(qtype == "toggle"){ int i; cin >> i; toggle(--i, t); debug(t, status, intervals); } else { int l, r; is_query[t] = 1; cin >> l >> r; --l, --r; auto next_ = intervals.upper_bound({l, -1, -1}); if(next_ != intervals.begin()){ next_--; if(next_->l <= l && r <= next_->r) ans[t] += t - next_->t; } a.pb({l, r, t, 0}); } debug(t); } CDQ(0, a.size()); rep1(i, q) if(is_query[i]) cout << ans[i] << '\n'; #ifdef DEBUG dbg::dout << "\nExecution time: " << clock() << "ms\n"; #endif return 0; }
#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...