Submission #357885

#	Time	Username	Problem	Language	Result	Execution time	Memory
357885		ogibogi2004	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1951 ms	66092 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+6;
struct BIT
{
	int a[MAXN];
	void update(int idx,int val)
	{
		for(;idx<MAXN;idx+=idx&(-idx))
		{
			a[idx]+=val;
		}
	}
	int query(int idx)
	{
		int ret=0;
		for(;idx>0;idx-=idx&(-idx))
		{
			ret+=a[idx];
		}
		return ret;
	}
}t1,t2;
int ans[MAXN];
struct point
{
	int x,y,z,ind,val;
	bool operator<(point const& other)const
	{
		if(x!=other.x)return x<other.x;
		if(y!=other.y)return y<other.y;
		return z<other.z;
	}
};
bool cmp(point p1,point p2)
{
	if(p1.y!=p2.y)return p1.y<p2.y;
	if(p1.z!=p2.z)return p1.z>p2.z;
	return p1.ind==0;
}
vector<point>v;
void dq(int l,int r)
{
	if(l+1==r)return;
	int mid=(l+r)/2;
	dq(l,mid);
	dq(mid,r);
	vector<point>tmp;
	vector<pair<int,int> >changes;
	int i1=l,i2=mid;
	while(i1<mid&&i2<r)
	{
		if(cmp(v[i1],v[i2]))
		{
			tmp.push_back(v[i1]);
			t1.update(v[i1].z,v[i1].val);
			if(v[i1].val>0)t2.update(v[i1].z,-1);
			if(v[i1].val<0)t2.update(v[i1].z,+1);
			changes.push_back({v[i1].z,v[i1].val});
			i1++;
		}
		else
		{
			tmp.push_back(v[i2]);
			//cout<<v[i2].ind<<" "<<t.query(MAXN-1)<<" "<<t.query(v[i2].z-1)<<endl;
			ans[v[i2].ind]+=(t1.query(MAXN-1)-t1.query(v[i2].z-1))+v[i2].x*(t2.query(MAXN-1)-t2.query(v[i2].z-1));
			i2++;
		}
	}
	while(i1<mid)
	{
		tmp.push_back(v[i1]);
		i1++;
	}
	while(i2<r)
	{
		tmp.push_back(v[i2]);
		ans[v[i2].ind]+=(t1.query(MAXN-1)-t1.query(v[i2].z-1))+v[i2].x*(t2.query(MAXN-1)-t2.query(v[i2].z-1));
		i2++;
	}
	for(int i=0;i<tmp.size();i++)v[l+i]=tmp[i];
	for(auto xd:changes)
	{
		t1.update(xd.first,-xd.second);
		if(xd.second>0)t2.update(xd.first,+1);
		if(xd.second<0)t2.update(xd.first,-1);
	}
}
set<pair<int,int> >segments;
bool lit[MAXN];
#define time aver
int n,q,time;
void pog_insert(int l,int r)
{
	v.push_back({time,l,r,0,-time});
	segments.insert({l,r});
}
void pog_erase(int l,int r)
{
	v.push_back({time,l,r,0,+time});
	segments.erase(make_pair(l,r));
}
void toggle(int i)
{
	if(lit[i]==1)
	{
		auto tt=segments.lower_bound({i+1,-69});
		tt--;
		int l=(*tt).first,r=(*tt).second;
		if(l<=i-1)pog_insert(l,i-1);
		if(i+1<=r)pog_insert(i+1,r);
		pog_erase(l,r);
		lit[i]=0;
	}
	else
	{
		if(!lit[i-1]&&!lit[i+1])
		{
			pog_insert(i,i);
		}
		else if(!lit[i-1]&&lit[i+1])
		{
			auto tt=segments.lower_bound({i,-69});
			int l=(*tt).first,r=(*tt).second;
			pog_erase(l,r);
			pog_insert(i,r);
		}
		else if(lit[i-1]&&!lit[i+1])
		{
			auto tt=segments.lower_bound({i,-69});
			tt--;
			int l=(*tt).first,r=(*tt).second;
			pog_erase(l,r);
			pog_insert(l,i);
		}
		else
		{
			auto tt=segments.lower_bound({i,-69});
			int l1=(*tt).first,r1=(*tt).second;
			tt--;
			int l2=(*tt).first,r2=(*tt).second;
			pog_erase(l1,r1);
			pog_erase(l2,r2);
			pog_insert(l2,r1);
		}
		lit[i]=!lit[i];
	}
}
int main()
{
	cin>>n>>q;
	time++;
	for(int i=1;i<=n;i++)
	{
		char c;cin>>c;
		if(c=='1')toggle(i);
	}
	int cnt=0;
	for(int i=1;i<=q;i++)
	{
		time++;
		string op;
		cin>>op;
		if(op=="toggle")
		{
			int x;
			cin>>x;
			toggle(x);
		}
		else
		{
			cnt++;
			int a,b;
			cin>>a>>b;b--;
			v.push_back({time,a,b,cnt,0});
		}
	}
	sort(v.begin(),v.end());
	/*for(int i=0;i<v.size();i++)
	{
		cout<<v[i].x<<" "<<v[i].y<<" "<<v[i].z<<" "<<v[i].ind<<" "<<v[i].val<<endl;
	}*/
	dq(0,v.size());
	/*cout<<endl<<endl;
	for(int i=0;i<v.size();i++)
	{
		cout<<v[i].x<<" "<<v[i].y<<" "<<v[i].z<<" "<<v[i].ind<<" "<<v[i].val<<endl;
	}*/
	for(int i=1;i<=cnt;i++)
	{
		cout<<ans[i]<<"\n";
	}
	//cout<<endl;
return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void dq(int, int)':
street_lamps.cpp:81:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int i=0;i<tmp.size();i++)v[l+i]=tmp[i];
      |              ~^~~~~~~~~~~

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