제출 #230593

#제출 시각아이디문제언어결과실행 시간메모리
230593lyc가로등 (APIO19_street_lamps)C++14
20 / 100
1431 ms56476 KiB
#include <bits/stdc++.h> using namespace std; #define TRACE(x) cerr << #x << " :: " << x << endl #define _ << " " << #define SZ(x) (int)(x).size() #define ALL(x) (x).begin(),(x).end() #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define RFOR(i,a,b) for (int i=(a);i>=(b);--i) using ll=long long; const int MX_N = 3e5+5; const int MX_Q = 3e5+5; int N, Q; string S; vector<array<int,2>> change; vector<array<int,3>> query; vector<array<int,4>> itv; set<array<int,2>> cur; int ans[MX_Q]; struct FenwickTree { vector<ll> ft; int n; void init(int _n) { n = _n; ft.assign(n+1,0); } void update(int i, int x) { for (; i <= n; i += i&-i) ft[i] += x; } ll query(int i) { ll s = 0; for (; i; i -= i&-i) s += ft[i]; return s; } ll query(int i, int j) { return query(j)-query(i-1); } } ft, ft2; void cdq(int l, int r, vector<array<int,4>>& a, vector<array<int,3>>& b) { if (l > r) return; if (l == r) { for (auto& x : a) { ft.update(x[1], (x[3]?1:-1)*x[0]); ft2.update(x[1], (x[3]?-1:1)); } for (auto& y : b) { ans[y[0]] += ft.query(y[1]); ans[y[0]] += ft2.query(y[1]) * y[0]; } for (auto& x : a) { ft.update(x[1], -(x[3]?1:-1)*x[0]); ft2.update(x[1], -(x[3]?-1:1)); } return; } int m = (l+r) >> 1; vector<array<int,4>> a1, a2; for (auto& x : a) (x[0] <= m ? a1 : a2).push_back(x); vector<array<int,3>> b1, b2; for (auto& y : b) (y[0] <= m ? b1 : b2).push_back(y); cdq(l,m,a1,b1); cdq(m+1,r,a2,b2); sort(ALL(a1), [](array<int,4> p, array<int,4> q){ return (p[2]>q[2]||(p[2]==q[2]&&(p[1]>q[1]||(p[1]==q[1]&&p[0]>q[0])))); }); sort(ALL(b2), [](array<int,3> p, array<int,3> q){ return (p[2]>q[2]||(p[2]==q[2]&&(p[1]>q[1]||(p[1]==q[1]&&p[0]>q[0])))); }); //TRACE(l _ r); //for (auto& x : a) TRACE(x[0] _ x[1] _ x[2] _ x[3]); //for (auto& y : b) TRACE(y[0] _ y[1] _ y[2]); //cout << endl; int i, j; for (i = 0, j = 0; i < SZ(a1) || j < SZ(b2); ) { if (i < SZ(a1) && (j >= SZ(b2) || a1[i][2] >= b2[j][2])) { ft.update(a1[i][1], (a1[i][3]?1:-1)*a1[i][0]); ft2.update(a1[i][1], (a1[i][3]?-1:1)); ++i; } else { ans[b2[j][0]] += ft.query(b2[j][1]); ans[b2[j][0]] += ft2.query(b2[j][1]) * b2[j][0]; ++j; } } for (;j < SZ(b2);) { ans[b2[j][0]] += ft.query(b2[j][1]); ans[b2[j][0]] += ft2.query(b2[j][1]) * b2[j][0]; ++j; } FOR(k,0,i-1){ ft.update(a1[k][1], -(a1[k][3]?1:-1)*a1[k][0]); ft2.update(a1[k][1], -(a1[k][3]?-1:1)); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N >> Q >> S; S = '^' + S + '0'; FOR(i,1,Q){ string T; cin >> T; if (T == "toggle") { int I; cin >> I; change.push_back({i,I}); } else { int A, B; cin >> A >> B; --B; query.push_back({i,A,B}); } } int len = 0; FOR(i,1,N+1){ if (S[i] == '0') { if (len) { cur.insert({i-len,i-1}); itv.push_back({0,i-len,i-1,0}); } len = 0; } else ++len; } for (auto& x : change) { //cout << x[1] << ' ' << x[1] << " vs "; //for (auto& y : cur) cout << y[0] << ' ' << y[1] << " | "; //cout << endl; if (S[x[1]] == '0') { auto it = cur.upper_bound({x[1],0}); array<int,2> y = {x[1],x[1]}; if (it != cur.end() && y[1]+1 == (*it)[0]) { auto z = *it; cur.erase(it); itv.push_back({x[0],z[0],z[1],1}); y[1] = z[1]; it = cur.upper_bound({x[1],0}); } if (it != cur.begin() && (*(--it))[1]+1 == y[0]) { auto z = *it; cur.erase(it); itv.push_back({x[0],z[0],z[1],1}); y[0] = z[0]; } cur.insert(y); itv.push_back({x[0],y[0],y[1],0}); S[x[1]] = '1'; } else { auto it = cur.upper_bound({x[1],0}); assert(it != cur.begin()); auto y = *(--it); cur.erase(it); assert(y[1] >= x[1]); itv.push_back({x[0],y[0],y[1],1}); if (y[0] < x[1]) { cur.insert({y[0],x[1]-1}); itv.push_back({x[0],y[0],x[1]-1,0}); } if (x[1] < y[1]) { cur.insert({x[1]+1,y[1]}); itv.push_back({x[0],x[1]+1,y[1],0}); } S[x[1]] = '0'; } } for (auto& x : cur) { itv.push_back({Q,x[0],x[1],1}); } //for (auto& x : itv) { TRACE(x[0] _ x[1] _ x[2] _ x[3]); } memset(ans,0,sizeof ans); ft.init(N); ft2.init(N); cdq(0,Q,itv,query); for (auto& q : query) { cout << ans[q[0]] << '\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...