Submission #163714

#	Time	Username	Problem	Language	Result	Execution time	Memory
163714		TadijaSebez	영역 (JOI16_ho_t4)	C++11	100 / 100	885 ms	97772 KiB

2016_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
const int inf=1e9+7;
int n,k;
char s[N];
int dx,dy;
map<pair<ll,int>,set<int>> ps,qs;
map<pair<ll,int>,set<pair<ll,ll>>> intervals;
map<pair<ll,int>,int> Y;
vector<pair<int,int>> sq;
map<pair<ll,int>,int> dp;
int md(int x, int dx){ return (x%dx+dx)%dx;}
void SQ(int x, int y)
{
	ll z=(ll)y*dx-(ll)x*dy;
	Y[{z,x}]=y;
	qs[{z,md(x,dx)}].insert(x);
	sq.pb({x,y});
}
void Add(int x, int y)
{
	ll z=(ll)y*dx-(ll)x*dy;
	ps[{z,md(x,dx)}].insert(x);
	SQ(x,y);
	SQ(x-1,y);
	SQ(x,y-1);
	SQ(x-1,y-1);
}
int Get(int x, int y)
{
	ll z=(ll)y*dx-(ll)x*dy;
	auto it=ps[{z,md(x,dx)}].lower_bound(x);
	if(it==ps[{z,md(x,dx)}].end()) return inf;
	assert((*it-x)%dx==0);
	return (*it-x)/dx;
}
void Solve()
{
	int x=0,y=0;
	Add(x,y);
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='E') y++;
		if(s[i]=='W') y--;
		if(s[i]=='N') x++;
		if(s[i]=='S') x--;
		Add(x,y);
	}
	ll ans=0;
	sort(sq.begin(),sq.end());
	sq.erase(unique(sq.begin(),sq.end()),sq.end());
	for(auto q:sq)
	{
		tie(x,y)=q;
		ll z=(ll)y*dx-(ll)x*dy;
		dp[q]=max({Get(x,y),Get(x+1,y),Get(x,y+1),Get(x+1,y+1)});
		if(dp[q]<k) intervals[{z,md(x,dx)}].insert({x+(ll)dp[q]*dx,x+(ll)k*dx});
	}
	for(auto st:intervals)
	{
		ll r=-9e18;
		for(auto i:st.second)
		{
			ll a,b;tie(a,b)=i;
			if(r<a) ans+=(b-a)/dx,r=b;
			else if(r<b) ans+=(b-r)/dx,r=b;
		}
	}
	printf("%lld\n",ans);
}
void Brute()
{
	set<pair<int,int>> pp;
	int x=0,y=0;
	pp.insert({x,y});
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='E') y++;
		if(s[i]=='W') y--;
		if(s[i]=='N') x++;
		if(s[i]=='S') x--;
		pp.insert({x,y});
	}
	int ans=0;
	for(auto p:pp)
	{
		tie(x,y)=p;
		if(pp.count({x,y}) && pp.count({x+1,y}) && pp.count({x,y+1}) && pp.count({x+1,y+1})) ans++;
	}
	printf("%i\n",ans);
}
int main()
{
	int x=0,y=0;
	scanf("%i %i",&n,&k);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='E') y++;
		if(s[i]=='W') y--;
		if(s[i]=='N') x++;
		if(s[i]=='S') x--;
	}
	if(y<0) for(int i=1;i<=n;i++){ if(s[i]=='E') s[i]='W';else if(s[i]=='W') s[i]='E';}
	if(x<0) for(int i=1;i<=n;i++){ if(s[i]=='N') s[i]='S';else if(s[i]=='S') s[i]='N';}
	y=abs(y);x=abs(x);
	if(x==0)
	{
		for(int i=1;i<=n;i++)
		{
			if(s[i]=='E') s[i]='N';
			else if(s[i]=='W') s[i]='S';
			else if(s[i]=='N') s[i]='E';
			else if(s[i]=='S') s[i]='W';
		}
		swap(x,y);
	}
	dx=x;dy=y;
	if(dx==0) Brute();
	else Solve();
	return 0;
}

Compilation message (stderr)

2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
2016_ho_t4.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
  ~~~~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 62 / 62