#define LOCAL
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define db 0
#define EPS (1e-7) //0.0000001 the value
#define PI (acos((ld)-1.0))
#define MAXN (300006)
#define ll /*long long*/ int
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < (ll)ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll((x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline long long rand(long long x, long long y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;}string to_string(bool b){return (b ? "true" : "false");}template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A>string to_string(A v) {bool first = true;string res = "{";for (const auto &x : v) {if (!first) {res += ", ";}first = false;res += to_string(x);}res += "}";return res;}void degug_out() { cerr << endl; }template <typename Head, typename... Tail>void degug_out(Head H, Tail... T) {cerr << " " << to_string(H);degug_out(T...);}
#ifdef LOCAL
#define degug(...) cerr << "[" << #__VA_ARGS__ << "]:", degug_out(__VA_ARGS__)
#else
#define degug(...) 42
#define cerr if(0)cout
#endif
typedef struct node{
/*ll prior=0,size=0;*/ long long prior=0; int size=0;
ll val=0;//value stored in the array
ll sum=0;//whatever info you want to maintain in segtree for each node
ll lazy=0;//whatever lazy update you want to do
struct node *l,*r;
bool rev=0;
ll key = 0;
}node;
typedef node* pnode;
ll sz(pnode t){
return t?t->size:0;
}
void upd_sz(pnode t){
if(t)t->size=sz(t->l)+1+sz(t->r);
}
void lazy(pnode t){
if(!t || !t->lazy)return;
t->val+=t->lazy;//operation of lazy
t->sum+=t->lazy*sz(t);
if(t->l)t->l->lazy+=t->lazy;//propagate lazy
if(t->r)t->r->lazy+=t->lazy;
t->lazy=0;
}
void push(pnode it)
{
if(!it)return;
if(it && it->rev)
{
it->rev = false;
swap(it->l, it->r);
if(it->l) it->l->rev ^= true;
if(it->r) it->r->rev ^= true;
}
}
void reset(pnode t){
if(t)t->sum = t->val;//no need to reset lazy coz when we call this lazy would itself be propagated
}
void combine(pnode& t,pnode l,pnode r){//combining two ranges of segtree
if(!l || !r)return void(t = l?l:r);
t->sum = l->sum + r->sum;
}
void operation(pnode t){//operation of segtree
if(!t)return;
reset(t);//reset the value of current node assuming it now represents a single element of the array
lazy(t->l);lazy(t->r);//imp:propagate lazy before combining t->l,t->r;
push(t->l), push(t->r);
combine(t,t->l,t);
combine(t,t,t->r);
}
void split(pnode t,pnode &l,pnode &r,ll pos,ll add=0){
if(!t)return void(l=r=NULL);
lazy(t);push(t);
ll curr_pos = add + sz(t->l);
if(curr_pos<=pos)//element at pos goes to left subtree(l)
split(t->r,t->r,r,pos,curr_pos+1),l=t;
else
split(t->l,l,t->l,pos,add),r=t;
upd_sz(t);
operation(t);
}
void merge(pnode &t,pnode l,pnode r){ //l->leftarray,r->rightarray,t->resulting array
lazy(l);lazy(r);push(l); push(r);
if(!l || !r) t = l?l:r;
else if(l->prior>r->prior)merge(l->r,l->r,r),t=l;
else merge(r->l,l,r->l),t=r;
upd_sz(t);
operation(t);
}
void init(pnode &ret, ll val, ll key){// key is like "name" maybe index lol
// pnode ret = new node;
ret->prior=rand(0,1000000000000ll);ret->size=1;
ret->val=val;
ret->sum=0;ret->lazy=0;
ret->l=NULL, ret->r=NULL;
ret->key = key; ret->rev=0;
// return ret;
}
// x is key, pos is where u want put, val is value
void insert(pnode& t, ll pos, ll x, ll val = 0)
{
if(!t) return;
pnode t1, t2;
split(t, t1, t2, pos-1);
pnode nv = new node; init(nv,val,x);
merge(t1, t1, nv);
merge(t,t1,t2);
return;
}
// note: for implicit treap can only delete by position
void del_pos(pnode &t, ll pos, ll add = 0)
{
// assert(t);
lazy(t->l); lazy(t->r); push(t->l); push(t->r);
ll curr_pos = add + sz(t->l);
if(curr_pos == pos)
merge(t, t->l, t->r);
else
{
if(curr_pos > pos) del_pos(t->l, pos, add);
else del_pos(t->r, pos, add + 1 + sz(t->l));
}
upd_sz(t);
operation(t);
}
ll range_query(pnode t,ll l,ll r){//[l,r]
pnode L,mid,R;
split(t,L,mid,l-1);
split(mid,t,R,r-l);//note: r-l!!
ll ans = t->sum;
merge(mid,L,t);
merge(t,mid,R);
return ans;
}
void range_update(pnode t,ll l,ll r,ll val){//[l,r]
pnode L,mid,R;
split(t,L,mid,l-1);
split(mid,t,R,r-l);//note: r-l!!
t->lazy+=val; //lazy_update
merge(mid,L,t);
merge(t,mid,R);
}
void reverse (pnode t, ll l, ll r) {
pnode t1, t2, t3;
split (t, t1, t2, l-1);
split (t2, t2, t3, r-l);
t2->rev ^= true;
merge (t, t1, t2);
merge (t, t, t3);
}
void output (pnode t) {
if (!t) return;
push (t); lazy(t);
output (t->l);
cout<<t->key<<" "<<t->val<<" ;";
output (t->r);
}
ll n,q,A[MAXN];
struct node2D {
int s,e,m;
pnode v;vector<ll>pts;
node2D *l,*r;
node2D(ll _S, ll _E) {
s=_S,e=_E,m=(s+e)/2;
v=0;pts.clear();
if(s!=e){
l=new node2D(s,m);
r=new node2D(m+1,e);
}
}
void update(ll x, ll y, ll a, ll b, ll nv){
if(s==x&&e==y){
// assert(*lbd(pts,a)==a&&*lbd(pts,b)==b);
range_update(v,lbd(pts,a)-pts.begin(),lbd(pts,b)-pts.begin(),nv);
return;
}
if(x>m)r->update(x,y,a,b,nv);
else if(y<=m)l->update(x,y,a,b,nv);
else l->update(x,m,a,b,nv),r->update(m+1,y,a,b,nv);
return;
}
ll rmq(ll a, ll b) {
// cerr<<s<<' '<<e<<' '<<a<<' '<<b<<'\n';
if(s==e){
// assert(lbd(pts,b)!=pts.end()&&*lbd(pts,b)==b);
// cerr<<pts.size()<<'\n';
// assert(v);
// cerr<<sz(v)<<' '<<lbd(pts,b)-pts.begin()<<'\n';
return range_query(v,lbd(pts,b)-pts.begin(),lbd(pts,b)-pts.begin());
}
// assert(lbd(pts,b)!=pts.end()&&*lbd(pts,b)==b);
// cerr<<"sz: "<<sz(v)<<' '<<lbd(pts,b)-pts.begin()<<'\n';
ll add=range_query(v,lbd(pts,b)-pts.begin(),lbd(pts,b)-pts.begin());
if(a>m)return r->rmq(a,b)+add;
else return l->rmq(a,b)+add;
}
void range_put(ll x,ll y,ll a,ll b){
pts.pb(a);pts.pb(b);
if(s==x&&e==y){
return;
}
if(x>m)r->range_put(x,y,a,b);
else if(y<=m)l->range_put(x,y,a,b);
else l->range_put(x,m,a,b),r->range_put(m+1,y,a,b);
}
pnode tmp=0;
void handle() {
sort(all(pts));pts.resize(unique(all(pts))-pts.begin());
for(auto i:pts){
if(v){tmp=new node;init(tmp,0,0); merge(v,v,tmp); if(0)insert(v,sz(v),sz(v),0);}
else {v=new node;init(v,0,0);}
}
if(s==e)return;
l->handle();
r->handle();
}
} *seg;
set<ll>close;
pi find(ll x) {
ll l,r;
l=*--close.lower_bound(x);++l;
r=*close.upper_bound(x);
return pi(l,r);
}
vector<tuple<bool,ll,ll>>in;
bool toggle[MAXN];
bool noblock(ll a, ll b){
return *close.lower_bound(a)>=b;
}
int main()
{
FAST
cin>>n>>q;
FOR(i,0,n){ char ch; cin>>ch; A[i]=ch-'0'; toggle[i]=A[i];}
FOR(i,0,n)if(!A[i])close.ins(i);
close.ins(-1);close.ins(n);
seg=new node2D(0,n);
FOR(T,1,q+1){
string op;cin>>op;
if(op[0]=='t'){
ll x;cin>>x;--x;
toggle[x]^=1;
if(toggle[x]){
// all ranges that can be fully on
close.erase(x);
pi bounds=find(x);
// [bounds.f,x,x+1,bounds.s]
seg->range_put(bounds.f,x,x+1,bounds.s);
} else {
// all ranges that were fully on b4 this +i
pi bounds=find(x);
// [bounds.f,x,x+1,bounds.s]
seg->range_put(bounds.f,x,x+1,bounds.s);
close.ins(x);
}
in.pb(make_tuple(0,x,-1));
} else {
ll a,b;cin>>a>>b;--a,--b;
seg->range_put(a,a,b,b);
in.pb(make_tuple(1,a,b));
}
}
seg->handle();
FOR(i,0,n)toggle[i]=A[i];
close.clear();
FOR(i,0,n)if(!A[i])close.ins(i);
close.ins(-1);close.ins(n);
FOR(T,1,q+1){
ll op=get<0>(in[T-1]);
if(op==0){
ll x=get<1>(in[T-1]);
toggle[x]^=1;
if(toggle[x]){ // just on
close.erase(x);
pi bounds=find(x);
// [bounds.f,x,x+1,bounds.s]
seg->update(bounds.f,x,x+1,bounds.s,-T);// cerr<<"safe\n";
} else {
pi bounds=find(x);
// [bounds.f,x,x+1,bounds.s]
seg->update(bounds.f,x,x+1,bounds.s,T);// cerr<<"safe\n";
close.ins(x);
}
} else {
ll a=get<1>(in[T-1]),b=get<2>(in[T-1]);
ll add=0;
if(noblock(a,b)){
add=T;
}
cout<<seg->rmq(a,b)+add<<'\n';
}
}
}
Compilation message
street_lamps.cpp: In member function 'void node2D::handle()':
street_lamps.cpp:229:12: warning: unused variable 'i' [-Wunused-variable]
for(auto i:pts){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1049 ms |
33952 KB |
Output is correct |
| 2 |
Correct |
1435 ms |
38924 KB |
Output is correct |
| 3 |
Correct |
3048 ms |
62424 KB |
Output is correct |
| 4 |
Execution timed out |
5125 ms |
401728 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1784 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1708 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1528 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1272 KB |
Output is correct |
| 5 |
Runtime error |
3133 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1400 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1400 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1272 KB |
Output is correct |
| 5 |
Execution timed out |
5133 ms |
470844 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
1049 ms |
33952 KB |
Output is correct |
| 9 |
Correct |
1435 ms |
38924 KB |
Output is correct |
| 10 |
Correct |
3048 ms |
62424 KB |
Output is correct |
| 11 |
Execution timed out |
5125 ms |
401728 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
