Submission #132114

#	Time	Username	Problem	Language	Result	Execution time	Memory
132114		TadijaSebez	Alternating Current (BOI18_alternating)	C++11	100 / 100	483 ms	16240 KiB

alternating

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int M=2*N;
const int inf=1e9+7;
int ls[M],rs[M],tsz,root,lzy[M],mn[M],n,m;
void Set(int &c, int ss, int se, int qs, int qe, int f)
{
	if(qs>se || ss>qe) return;
	if(!c) c=++tsz;
	if(qs<=ss && qe>=se){ lzy[c]+=f;mn[c]+=f;return;}
	int mid=ss+se>>1;
	Set(ls[c],ss,mid,qs,qe,f);
	Set(rs[c],mid+1,se,qs,qe,f);
	mn[c]=min(mn[ls[c]],mn[rs[c]])+lzy[c];
}
void Set(int l, int r, int f)
{
	if(l>r)
	{
		Set(root,1,n,1,r,f);
		Set(root,1,n,l,n,f);
	}
	else Set(root,1,n,l,r,f);
}
int Get(int c, int ss, int se, int qs, int qe)
{
	if(qs>se || ss>qe) return inf;
	if(qs<=ss && qe>=se) return mn[c];
	int mid=ss+se>>1;
	return min(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe))+lzy[c];
}
int Get(int l, int r)
{
	if(l>r) return min(Get(root,1,n,1,r),Get(root,1,n,l,n));
	return Get(root,1,n,l,r);
}
int l[N],r[N];
vector<int> events[N],E[N];
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);}
int col[N];
bool was[N];
void DFS(int u)
{
	was[u]=1;
	for(int v:E[u])
	{
		if(!was[v])
		{
			col[v]=col[u]^1;
			DFS(v);
		}
		else if(col[u]==col[v])
		{
			printf("impossible\n");
			exit(0);
		}
	}
}
int main()
{
	scanf("%i %i",&n,&m);
	set<int> active;
	for(int i=1;i<=m;i++)
	{
		scanf("%i %i",&l[i],&r[i]);
		events[l[i]].pb(i);
		events[r[i]+1].pb(i);
		if(l[i]>r[i]) active.insert(i);
	}
    for(int i=1;i<=n;i++)
	{
		for(int j:events[i])
		{
			if(active.count(j)) active.erase(j);
			else active.insert(j);
		}
		if(active.size()<2) return 0*printf("impossible\n");
		if(active.size()==2) AddEdge(*active.begin(),*active.rbegin());
	}
	for(int i=1;i<=m;i++) if(!was[i]) DFS(i);
	for(int i=1;i<=m;i++) if(!col[i]) Set(l[i],r[i],1);
	for(int i=1;i<=m;i++)
	{
		if(col[i]) printf("0");
		else
		{
			if(Get(l[i],r[i])==1) printf("1");
			else
			{
				printf("0");
				Set(l[i],r[i],-1);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

alternating.cpp: In function 'void Set(int&, int, int, int, int, int)':
alternating.cpp:13:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
alternating.cpp: In function 'int Get(int, int, int, int, int)':
alternating.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
alternating.cpp: In function 'int main()':
alternating.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
alternating.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&l[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26