Submission #169158

#	Time	Username	Problem	Language	Result	Execution time	Memory
169158		ryansee	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	5133 ms	524292 KiB

street_lamps

#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 (stderr)

street_lamps.cpp: In member function 'void node2D::handle()':
street_lamps.cpp:229:12: warning: unused variable 'i' [-Wunused-variable]
   for(auto i:pts){
            ^

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20