#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)
#define NN 300010
#define M 1000000007 // 998244353
struct query {
enum {
INSERT,
QUERY
} type;
ll l, r; // [l, r]
ll time;
ll qidx;
query(ll l, ll r, ll time): l(l), r(r), time(time), type(INSERT) {}
query(ll l, ll r, ll time, ll qidx): l(l), r(r), time(time), qidx(qidx), type(QUERY) {}
};
ll ans[NN];
const ll INFTIME = NN;
namespace seg {
typedef pl T;
T id={0, 0};
T f(T a, T b) {return {a.K + b.K, a.V + b.V};}
T t[2 * NN];
ll n=NN; // array size
vl record;
void modify(ll p, T value) { // set value at position p
record.push_back(p);
for (p+=n, t[p] = f(t[p], value); p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
}
void reset() {
for (auto p: record) {
for (p+=n, t[p] = id; p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
}
record.clear();
}
T query(ll l, ll r) { // fold f on interval [l, r)
T resl=id, resr=id;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l&1) resl = f(resl, t[l++]);
if (r&1) resr = f(t[--r], resr);
}
return f(resl, resr);
}
}
void solve(vector<query>::iterator l, vector<query>::iterator r) {
if (r-l <= 1) return;
auto mid = l + (r-l)/2;
solve(l, mid); solve(mid, r);
auto cmp = [](const auto &a, const auto &b) {return a.l < b.l; };
sort(l, mid, cmp); sort(mid, r, cmp);
auto lit = l, rit = mid;
// cdq on {number of points (A <= (l <= r) <= B), sum of weights of ponits }
#define sgn(x) (x < 0 ? -1:1)
while (rit != r) {
if (lit != mid and lit->l <= rit->l) { // insert
auto [type, l, r, time, _] = *lit++;
if (type == query::INSERT) {
seg::modify(r, {(INFTIME - abs(time)) * sgn(time), sgn(time)});
}
} else {
auto [type, l, r, time, qidx] = *rit++;
if (type == query::QUERY) {
auto [contribution, number] = seg::query(r, NN);
contribution -= number * (INFTIME - time);
ans[qidx] += contribution;
}
}
}
seg::reset();
}
int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(20);
vector<query> queries;
G(n) G(q)
GS(s) set<pl> intervals;
// optimizzation: intstead of calling insert n times, just push back immidiately
auto insert = [&](ll i, ll time) {
pl to_add{i, i};
auto it = intervals.lower_bound({i, i});
if (it != intervals.end() and it->K == i+1) {
to_add.V = it->V;
queries.push_back(query(it->K, it->V, -time));
intervals.erase(it);
}
it = intervals.lower_bound({i, i});
if (it != intervals.begin() and (*--it).V == i-1) {
to_add.K = it->K;
queries.push_back(query(it->K, it->V, -time));
intervals.erase(it);
}
queries.push_back(query(to_add.K, to_add.V, time));
};
auto remove = [&](ll i, ll time) {
auto [l, r] = *--intervals.upper_bound({i, 1e9});
intervals.erase(--intervals.upper_bound({i, 1e9}));
queries.push_back(query(l, r, -time));
if (l < i-1) {
queries.push_back(query(l, i-1, time));
intervals.insert({l, i-1});
}
if (i + 1 < r) {
queries.push_back(query(i+1, r, time));
intervals.insert({i+1, r});
}
};
{
ll l = -1, r = -1;
F(i, 0, n) {
if (s[i] == '1') {
if (l == -1) l = i; r = i;
} else {
if (l != -1) {
intervals.insert({l, r});
queries.push_back(query(l, r, 1));
}
l = r = -1;
}
}
if (l != -1) {
intervals.insert({l, r});
queries.push_back(query(l, r, 1));
}
}
ll nq = 0; // qidx indexing
F(time, 2, q+2) {
GS(s)
if (s == "toggle") {
G(i) --i;
if (s[i] == '1') remove(i, time);
else insert(i, time);
s[i] ^=1;
} else {
G(a) G(b) --a, b-=2;
queries.push_back(query(a, b, time, nq++));
}
}
// for (auto [type, l, r, time, qidx]: queries) {
// cout << (type == query::INSERT ? "INS":"QUE") << " " << l << " " << r << " " << time << " " << qidx << endl;
// }
solve(A(queries));
F(i, 0, nq) cout << ans[i] << '\n';
}
Compilation message
street_lamps.cpp: In constructor 'query::query(ll, ll, ll)':
street_lamps.cpp:33:8: warning: 'query::time' will be initialized after [-Wreorder]
33 | ll time;
| ^~~~
street_lamps.cpp:31:7: warning: 'query::<unnamed enum> query::type' [-Wreorder]
31 | } type;
| ^~~~
street_lamps.cpp:36:5: warning: when initialized here [-Wreorder]
36 | query(ll l, ll r, ll time): l(l), r(r), time(time), type(INSERT) {}
| ^~~~~
street_lamps.cpp: In constructor 'query::query(ll, ll, ll, ll)':
street_lamps.cpp:34:8: warning: 'query::qidx' will be initialized after [-Wreorder]
34 | ll qidx;
| ^~~~
street_lamps.cpp:31:7: warning: 'query::<unnamed enum> query::type' [-Wreorder]
31 | } type;
| ^~~~
street_lamps.cpp:37:5: warning: when initialized here [-Wreorder]
37 | query(ll l, ll r, ll time, ll qidx): l(l), r(r), time(time), qidx(qidx), type(QUERY) {}
| ^~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:149:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
149 | if (l == -1) l = i; r = i;
| ^~
street_lamps.cpp:149:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
149 | if (l == -1) l = i; r = i;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
340 ms |
24488 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 2 |
Runtime error |
5 ms |
9300 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
