| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 688971 | QwertyPi | Street Lamps (APIO19_street_lamps) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct BIT{
vector<int> ip[300011], bit[300011];
void init(){
for(int i = 0; i < 300011; i++){
ip[i].push_back(0); sort(ip[i].begin(), ip[i].end());
ip[i].resize(unique(ip[i].begin(), ip[i].end()));
bit[i].resize(ip[i].size());
}
}
void init_add(int x, int y){
for(int i = x; i; i -= i & -i){
ip[i].push_back(y);
}
}
void add(int x, int y, int v){
for(int i = x; i < 300011; i += i & -i){
int y2 = lower_bound(bit[i].begin(), bit[i].end(), y) - bit[i].begin();
for(int j = y2; j < bit[i].size(); j += j & -j){
bit[i][j] += v;
}
}
}
int qry(int x, int y){
int ret = 0;
for(int i = x; i; i -= i & -i){
int y2 = upper_bound(bit[i].begin(), bit[i].end(), y) - bit[i].begin() - 1;
for(int j = y2; j; j -= j & -j){
ret += bit[i][j];
}
}
return ret;
}
} bit;
struct segment{
int l, r, t;
bool operator< (const segment& o) const {
return l < o.l || l == o.l && r < o.r;
}
};
vector<segment> segs[300011];
void add(const segment& s, int t2) {
cout << "ADD " << s.l << ' ' << s.r << ' ' << s.t << ' ' << t2 << endl;
init_add(s.l, s.r); segs[t2].push_back(s);
}
set<segment> S;
bool on[300011], isq[300011];
int L[300011], R[300011], rans[300011];
void show(){
for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
}
void toggle(int x, int t){
// cout << "TOGGLE " << x << ' ' << t << endl;
if(on[x]){
auto ptr = S.lower_bound({x, 1 << 30}); --ptr; int l = ptr->l, r = ptr->r; add(*ptr, t); S.erase(ptr);
if(on[x - 1]) { S.insert({l, x, t}); }
if(on[x + 1]) { S.insert({x + 1, r, t}); }
}else{
int l = x, r = x + 1;
if(on[x - 1]) { auto ptr = S.lower_bound({x, -1}); --ptr; l = ptr->l; add(*ptr, t); S.erase(ptr); }
if(on[x + 1]) { auto ptr = S.lower_bound({x, -1}); r = ptr->r; add(*ptr, t); S.erase(ptr); }
S.insert({l, r, t});
}
on[x] = !on[x];
// show();
}
void query(int l, int r, int t){
isq[t] = true; L[t] = l, R[t] = r;
auto ptr = S.lower_bound({l, 1 << 30});
if(ptr != S.begin() && prev(ptr)->l <= l && r <= prev(ptr)->r) rans[t] += t - prev(ptr)->t;
}
void query2(int l, int r, int t){
rans[t] += bit.qry(r, r) - bit.qry(l, r) - bit.qry(l, l) + bit.qry(r, r);
}
int32_t main(){
int n, q; cin >> n >> q;
string s; cin >> s; for(int i = 1; i <= n; i++) on[i] = s[i - 1] == '1';
vector<segment> v;
for(int i = 1; i <= n; i++) {
if(on[i]){
if(v.size() && v.back().r == i) v.back().r++; else v.push_back({i, i + 1, 0});
}
}
for(auto s : v) S.insert(s);
for(int t = 1; t <= q; t++){
string type; cin >> type;
if(type == "query"){
int l, r; cin >> l >> r;
query(l, r, t);
}else{
int x; cin >> x; toggle(x, t);
}
}
for(int t = 1; t <= q; t++){
for(auto s : segs[t]){
bit.add(s.l, s.r, t - s.t);
}
if(isq[t]){
query2(L[t], R[t], t);
}
}
for(int t = 1; t <= q; t++){
if(isq[t]){
cout << rans[t] << endl;
}
}
}