Submission #163364

#	Time	Username	Problem	Language	Result	Execution time	Memory
163364		TadijaSebez	Golf (JOI17_golf)	C++11	100 / 100	4345 ms	492892 KiB

golf

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
const int H=4*N;
const int inf=1e9+7;
struct compress
{
	vector<int> all;
	void Add(int x){ all.pb(x);}
	void Build(){ sort(all.begin(),all.end());all.erase(unique(all.begin(),all.end()),all.end());}
	int Get(int x){ return lower_bound(all.begin(),all.end(),x)-all.begin()+1;}
	int sz(){ return all.size();}
} xs,ys;
struct rec
{
	int type,x,l,r;
	rec(int t, int a, int b, int c):type(t),x(a),l(b),r(c){}
};
vector<rec> rs;
int X1[N],Y1[N],X2[N],Y2[N];
vector<pair<int,int>> Add[H],Del[H];
vector<int> fir,las;
int n,sx,sy,ex,ey;
void Build(int type)
{
	for(int i=1;i<=n;i++) Add[X1[i]].pb({Y1[i],Y2[i]}),Del[X2[i]].pb({Y1[i],Y2[i]});
    set<pair<int,int>> st;
    st.insert({1,1});st.insert({ys.sz(),ys.sz()});
    for(int x=1;x<=xs.sz();x++)
	{
        for(auto p:Del[x])
		{
			auto it=st.find(p),l=it,r=it;l--;r++;
			rs.pb(rec(type,x,l->second,r->first));
			st.erase(it);
		}
		if(sx==x)
		{
			auto r=st.lower_bound({sy,-inf}),l=r;l--;
			fir.pb(rs.size());
			rs.pb(rec(type,x,l->second,r->first));
		}
		if(ex==x)
		{
			auto r=st.lower_bound({ey,-inf}),l=r;l--;
			las.pb(rs.size());
			rs.pb(rec(type,x,l->second,r->first));
		}
		for(auto p:Add[x])
		{
			st.insert(p);
			auto it=st.find(p),l=it,r=it;l--;r++;
			rs.pb(rec(type,x,l->second,r->first));
		}
	}
	for(int i=1;i<=xs.sz();i++) Add[i].clear(),Del[i].clear();
	for(int i=1;i<=n;i++) swap(X1[i],Y1[i]),swap(X2[i],Y2[i]);swap(sx,sy);swap(ex,ey);swap(xs,ys);
}
const int M=H*2;
bool was[H];
int dist[H];
queue<int> q;
struct SegmentTree
{
	set<pair<int,int>> node[M];
	SegmentTree(){}
	void Ins(int x, int l, int r, int id)
	{
		for(l+=H,r+=H;l<=r;l>>=1,r>>=1)
		{
			if(l%2==1) node[l++].insert({x,id});
			if(r%2==0) node[r--].insert({x,id});
		}
	}
	void Take(int x, int l, int r, int d)
	{
		for(x+=H;x;x>>=1)
		{
			for(auto it=node[x].lower_bound({l,-inf});it!=node[x].end() && it->first<=r;node[x].erase(it++))
			{
				int id=it->second;
				if(!was[id]) was[id]=1,dist[id]=d+1,q.push(id);
			}
		}
	}
} ST[2];
int main()
{
	scanf("%i %i %i %i",&sx,&sy,&ex,&ey);
	scanf("%i",&n);
	xs.Add(0);xs.Add(inf);ys.Add(0);ys.Add(inf);xs.Add(sx);xs.Add(ex);ys.Add(sy);ys.Add(ey);
	for(int i=1;i<=n;i++) scanf("%i %i %i %i",&X1[i],&X2[i],&Y1[i],&Y2[i]),xs.Add(X1[i]),xs.Add(X2[i]),ys.Add(Y1[i]),ys.Add(Y2[i]);
	xs.Build();ys.Build();
	sx=xs.Get(sx);ex=xs.Get(ex);sy=ys.Get(sy);ey=ys.Get(ey);
	for(int i=1;i<=n;i++) X1[i]=xs.Get(X1[i]),X2[i]=xs.Get(X2[i]),Y1[i]=ys.Get(Y1[i]),Y2[i]=ys.Get(Y2[i]);
	Build(0);Build(1);
	for(int i=0;i<rs.size();i++) ST[rs[i].type].Ins(rs[i].x,rs[i].l,rs[i].r,i);
	for(int i:fir)
	{
		if(rs[i].type==0)
		{
			if(ex==rs[i].x && ey>=rs[i].l && ey<=rs[i].r) return 0*printf("1\n");
		}
		else
		{
			if(ey==rs[i].x && ex>=rs[i].l && ex<=rs[i].r) return 0*printf("1\n");
		}
		q.push(i),was[i]=1;
	}
	while(q.size())
	{
		int x=q.front();
		q.pop();
		ST[rs[x].type^1].Take(rs[x].x,rs[x].l,rs[x].r,dist[x]);
	}
	int ans=1e9+7;
	for(int i:las) if(was[i]) ans=min(ans,dist[i]);
	printf("%i\n",ans+1);
	return 0;
}

Compilation message (stderr)

golf.cpp: In function 'void Build(int)':
golf.cpp:59:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i=1;i<=n;i++) swap(X1[i],Y1[i]),swap(X2[i],Y2[i]);swap(sx,sy);swap(ex,ey);swap(xs,ys);
  ^~~
golf.cpp:59:60: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int i=1;i<=n;i++) swap(X1[i],Y1[i]),swap(X2[i],Y2[i]);swap(sx,sy);swap(ex,ey);swap(xs,ys);
                                                            ^~~~
golf.cpp: In function 'int main()':
golf.cpp:99:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<rs.size();i++) ST[rs[i].type].Ins(rs[i].x,rs[i].l,rs[i].r,i);
              ~^~~~~~~~~~
golf.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i %i",&sx,&sy,&ex,&ey);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
golf.cpp:94:114: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i %i %i",&X1[i],&X2[i],&Y1[i],&Y2[i]),xs.Add(X1[i]),xs.Add(X2[i]),ys.Add(Y1[i]),ys.Add(Y2[i]);
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70