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;
#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++)
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--)
#define ii pair<int, int>
#define fi first
#define se second
#define vi vector<int>
#define eb emplace_back
#define em emplace
#define sp ' '
#define endl '\n'
//#define int long long
const int maxn = 5e5 + 5;
int n, q;
char c[maxn];
string tp[maxn];
int id[maxn];
bool state[maxn];
int ans[maxn];
struct it {
vi mn, mx; // min, max of off ones
it (int len= 1) {
mn = vi(4 * len + 5, n);
mx = vi(4 * len + 5, 0);
build(1, 1, len);
}
void build(int u, int l, int r) {
if(l == r) mn[u] = mx[u] = l;
else {
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
mn[u] = l;
mx[u] = r;
}
}
void sett(int u, int l, int r, int p, bool on) {
if(l > p or p > r) return;
if(l == r) {
mn[u] = !on? p: n;
mx[u] = !on? p: 0;
}
else {
int mid = l + r >> 1;
sett(u << 1, l, mid, p, on);
sett(u << 1 | 1, mid + 1, r , p, on);
mn[u] = min(mn[u << 1], mn[u << 1 | 1]);
mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
}
}
int get_min(int u, int l, int r, int ll, int rr) {
if(l > rr or ll > r) return n;
if(ll <= l and r <= rr) return mn[u];
int mid = l + r >> 1;
return min(get_min(u << 1, l, mid, ll, rr), get_min(u << 1 | 1, mid + 1, r, ll, rr));
}
int get_max(int u, int l, int r, int ll, int rr) {
if(l > rr or ll > r) return 0;
if(ll <= l and r <= rr) return mx[u];
int mid = l + r >> 1;
return max(get_max(u << 1, l, mid, ll, rr), get_max(u << 1 | 1, mid + 1, r, ll, rr));
}
} IT;
struct bit {
vector<pair<ii, ii> > qrs;
vector<vi> vals;
vector<vi> sum;
vector<int> res;
bit(int len = 0) {
vals.resize(len + 10);
sum.resize(len + 10);
}
void add(int x, int y, int v) {
qrs.eb(ii(0, v), ii(x, y));
for(int i = x; i < sum.size(); i += i & -i) {
vals[i].eb(y);
}
}
void get(int x, int y) {
qrs.eb(ii(1, 0), ii(x, y));
for(int i = x; i > 0; i -= i & -i) {
vals[i].eb(y);
}
}
void real_add(int x, int y, int v) {
for(int i = x; i < sum.size(); i += i &-i) {
for(int j = lower_bound(begin(vals[i]), end(vals[i]), y) - begin(vals[i]) + 1; j > 0; j -= j & -j) {
sum[i][j] += v;
}
}
}
int real_get(int x, int y) {
int r = 0;
for(int i = x; i > 0; i -= i &-i) {
for(int j = lower_bound(begin(vals[i]), end(vals[i]), y) - begin(vals[i]) + 1; j < sum[i].size(); j += j & -j) {
r += sum[i][j];
}
}
return r;
}
void process() {
fori(i, 1, sum.size() - 1) {
sort(begin(vals[i]),end(vals[i]));
sum[i].resize(vals[i].size() + 5);
}
for(auto t: qrs) {
if(t.fi.fi == 0) {
int v= t.fi.se;
int x = t.se.fi, y = t.se.se;
real_add(x, y, v);
}
else {
int x = t.se.fi, y = t.se.se;
res.eb(real_get(x, y));
}
}
}
} BIT;
void turn_on(int i, int t) {
int L = IT.get_max(1, 1, n - 1, 1, i - 1) + 1;
int R = IT.get_min(1, 1, n - 1, i + 1, n - 1) - 1;
IT.sett(1, 1, n - 1, i, 1);
BIT.add(L, R + 1, -t);
BIT.add(L, i, t);
BIT.add(i + 1, R + 1, t);
state[i] = 1;
}
void turn_off(int i, int t) {
int L = IT.get_max(1, 1, n - 1, 1, i - 1) + 1;
int R = IT.get_min(1, 1, n - 1, i + 1, n - 1) - 1;
IT.sett(1, 1, n - 1, i, 0);
BIT.add(L, R + 1, t);
BIT.add(L, i, -t);
BIT.add(i + 1, R + 1, -t);
state[i] = 0;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
n++;
IT = it(n - 1);
BIT = bit(n);
fori(i, 1, n - 1) {
cin >> c[i];
if(c[i] == '1') turn_on(i, 0);
}
fori(i, 1, q) {
cin >> tp[i];
if(tp[i] == "toggle") {
cin >> id[i];
if(state[id[i]] == 0) turn_on(id[i], i);
else if(state[id[i]] == 1) turn_off(id[i], i);
}
else {
int l, r;
cin >> l >> r;
BIT.get(l, r);
if(IT.get_min(1, 1, n - 1, l, r - 1) >= r) ans[i] += i;
}
}
BIT.process();
auto temp = BIT.res;
// cout << temp.size() << endl;
int pt = 0;
fori(i, 1, q) {
if(tp[i] == "query") {
ans[i] += temp[pt++];
cout << ans[i] << endl;
}
}
}
Compilation message (stderr)
street_lamps.cpp: In member function 'void it::build(int, int, int)':
street_lamps.cpp:32:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int mid = l + r >> 1;
| ~~^~~
street_lamps.cpp: In member function 'void it::sett(int, int, int, int, bool)':
street_lamps.cpp:46:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mid = l + r >> 1;
| ~~^~~
street_lamps.cpp: In member function 'int it::get_min(int, int, int, int, int)':
street_lamps.cpp:57:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int mid = l + r >> 1;
| ~~^~~
street_lamps.cpp: In member function 'int it::get_max(int, int, int, int, int)':
street_lamps.cpp:63:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int mid = l + r >> 1;
| ~~^~~
street_lamps.cpp: In member function 'void bit::add(int, int, int)':
street_lamps.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int i = x; i < sum.size(); i += i & -i) {
| ~~^~~~~~~~~~~~
street_lamps.cpp: In member function 'void bit::real_add(int, int, int)':
street_lamps.cpp:94:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i = x; i < sum.size(); i += i &-i) {
| ~~^~~~~~~~~~~~
street_lamps.cpp: In member function 'int bit::real_get(int, int)':
street_lamps.cpp:104:85: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int j = lower_bound(begin(vals[i]), end(vals[i]), y) - begin(vals[i]) + 1; j < sum[i].size(); j += j & -j) {
| ~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |