//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//# include <x86intrin.h>
# include <bits/stdc++.h>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y) for (ll i = x; i <= y; i ++)
#define FOr(i,x,y) for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to... Red
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
// cin.exceptions(cin.failbit);
// throws exception when do smth illegal
// ex. try to read letter into int
if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}
const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 3e5 + 3;
const int M = 22;
const int pri = 997;
const int Magic = 2101;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
int rnd (int l, int r) {
return uniform_int_distribution<int> (l, r)(gen);
}
set < array<int,3> > act;
//on segments l, r, st_time
int n, m;
string s;
int t[N*18*18];
int L[N*18*18];
int R[N*18*18];
int root[N];
int ptr;
void updQuery (int l, int r, int x, int &v, int tl = 1, int tr = N) {
if (tl > r || l > tr || l > r) return;
if (!v) v = ++ptr;
if (l <= tl && tr <= r) {
t[v] += x;
return;
}
int tm = (tl+tr)>>1;
updQuery(l, r, x, L[v], tl, tm);
updQuery(l, r, x, R[v], tm+1, tr);
}
int getQuery (int p, int v, int tl = 1, int tr = N) {
if (tl == tr || !v) {
return t[v];
}
int tm = (tl+tr)>>1;
if(p <= tm) return t[v] + getQuery(p, L[v], tl, tm);
return t[v] + getQuery(p, R[v], tm+1, tr);
}
int getCalc (int v, int r) {
int res = 0;
while(v) {
res += getQuery(r, root[v]);
v -= (v&-v);
}
return res;
}
void updRec (int v, int l, int r, int x) {
while(v < N) {
updQuery(l, r, x, root[v]);
v += (v&-v);
}
}
void turn_off (int pos, int i) {
auto cur = *prev(act.lb({pos+1, 0, 0}));
updRec (cur[0], cur[0], cur[1], i-cur[2]);
updRec (cur[1]+1, cur[0], cur[1], cur[2]-i);
act.erase(cur);
act.insert({cur[0], pos, i});
act.insert({pos+1, cur[1], 1});
}
void turn_on (int pos, int i) {
auto curL = *prev(act.lb({pos+1, 0, 0}));
auto curR = *prev(act.lb({pos+2, 0, 0}));
updRec (curL[0], curL[0], curL[1], i-curL[2]);
updRec (curL[1]+1, curL[0], curL[1], curL[2]-i);
updRec (curR[0], curR[0], curR[1], i-curR[2]);
updRec (curR[1]+1, curR[0], curR[1], curR[2]-i);
act.erase(curL);
act.erase(curR);
act.insert({curL[0], curR[1], i});
}
int main () {
SpeedForce;
cin >> n >> m >> s;
s='0'+s;
for (auto &e : s) e -= '0';
for (int i = 1; i <= n; ++i) {
{
int j = i;
while(j <= n && s[j]) ++j;
act.insert({i, j, 0});
i = j;
}
}
for (int i = 1; i <= m; ++i) {
string op;
cin >> op;
if (op[0] == 't') {
int pos;
cin >> pos;
if(s[pos]) {
turn_off(pos, i);
} else {
turn_on(pos, i);
}
s[pos] ^= 1;
} else {
int l, r;
cin >> l >> r;
//in rectangle x = {1, l} y = {1, r}
int ans = getCalc(l, r);
auto cur = *prev(act.lb({l+1, 0, 0}));
if (cur[1] >= r) ans += i-cur[2];
cout << ans << '\n';
}
}
return Accepted;
}
// B...a
Compilation message
street_lamps.cpp: In function 'void setIn(std::string)':
street_lamps.cpp:34:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
34 | void setIn(string s) { freopen(s.c_str(),"r",stdin); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void setOut(std::string)':
street_lamps.cpp:35:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
35 | void setOut(string s) { freopen(s.c_str(),"w",stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1238 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1152 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
5 ms |
896 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3864 ms |
198092 KB |
Output is correct |
| 6 |
Correct |
2796 ms |
170040 KB |
Output is correct |
| 7 |
Correct |
1754 ms |
131232 KB |
Output is correct |
| 8 |
Correct |
133 ms |
8736 KB |
Output is correct |
| 9 |
Incorrect |
101 ms |
4088 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
768 KB |
Output is correct |
| 3 |
Correct |
6 ms |
896 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
476 ms |
24380 KB |
Output is correct |
| 6 |
Correct |
1210 ms |
100708 KB |
Output is correct |
| 7 |
Correct |
2061 ms |
127160 KB |
Output is correct |
| 8 |
Correct |
2832 ms |
145040 KB |
Output is correct |
| 9 |
Incorrect |
1597 ms |
4524 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
