Submission #125534

#	Time	Username	Problem	Language	Result	Execution time	Memory
125534		Retro3014	영역 (JOI16_ho_t4)	C++17	100 / 100	225 ms	17768 KiB

2016_ho_t4

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, K;
string str;
vector<pii> vt;



map<pii, vector<int> > mp; 

vector<pii> mrg;
vector<int> tmp;
vector<pii> mrg2;
vector<pii> mrg3;

ll ans;

void merge(){
	//cout<<"****************"<<endl;
	mrg2.clear();
	for(int i=0; i<tmp.size(); i++){
		mrg2.pb({tmp[i], tmp[i] + K-1});
	//	cout<<tmp[i]<<" "<<tmp[i]+K-1<<endl;
	}
	if(mrg.empty() || mrg2.empty()){
		mrg.clear(); return;
	}
	//cout<<"========="<<endl;
	//for(int i=0; i<mrg.size(); i++){
	//	cout<<mrg[i].first<<" "<<mrg[i].second<<endl;
	//}
	//cout<<"========="<<endl;
	int t1 = mrg[0].first; int t2 = mrg2[0].first;
	int n1 = 0, n2 = 0;
	int i1=0, i2=0;
	int cnt1=0, cnt2=0;
	int now = -INF, prv=-INF;
	while(1){
		//cout<<"n "<<t1<<" "<<t2<<endl;
		if(t1<t2 || (t1==t2 && n1==0)){
			now = max(now, t1);
			if(n1!=1){
				cnt1++;
				t1 = mrg[i1].second;
				n1 = 1;
			}else{
				n1 = 0;
				cnt1--;
				i1++;
				if(i1>=mrg.size()){
					if(prv!=-INF){
						mrg3.pb({prv, now});
					}
					break;
				}
				t1 = mrg[i1].first;
			}
		}else{
			now = max(now, t2);
			if(n2!=1){
				cnt2++;
				while(i2+1<mrg2.size() && mrg2[i2+1].first<=mrg2[i2].second){
					i2++;
				}
				t2 = mrg2[i2].second;
				n2 = 1;
			}else{
				n2 = 0;
				cnt2--;
				i2++;
				if(i2>=mrg2.size()){
					if(prv!=-INF){
						mrg3.pb({prv, now});
					}
					break;
				}
				t2 = mrg2[i2].first;
			}
		}
		if(cnt1>0 && cnt2>0){
			if(prv==-INF){
				prv = now;
			}
		}else{
			if(prv!=-INF){
				mrg3.pb({prv, now});
				prv = -INF;
			}
		}
	}
	mrg = mrg3;
	mrg3.clear();
	//for(int i=0; i<mrg.size(); i++){
	//	cout<<mrg[i].first<<" "<<mrg[i].second<<endl;
	//}
	return;
}

int main(){
	scanf("%d%d", &N, &K);
	cin>>str;
	int x = 0, y = 0;
	for(int i=1; i<=N+1; i++){
		vt.pb({x, y});
		if(i==N+1)	break;
		if(str[i-1]=='N'){
			y++;
		}else if(str[i-1]=='E'){
			x++;
		}else if(str[i-1]=='W'){
			x--;
		}else{
			y--;
		}
	}
	if(x==0){
		int tmp = x; x = y; y = tmp;
		for(int i=0; i<vt.size(); i++){
			tmp = vt[i].first; vt[i].first = vt[i].second; vt[i].second = tmp;
		}
	}
	//cout<<x<<" "<<y<<endl;
	for(int i=0; i<vt.size(); i++){
		int t;
		if(x==0){
			t = 0;
		}else if(x<0){
			if(vt[i].first==0){
				t = 0;
			}
			else if(vt[i].first>0){
				t = vt[i].first / x;
			}else{
				t = vt[i].first / x + (((vt[i].first/x) * x ==vt[i].first)?0:1);
			}
		}else{
			if(vt[i].first==0){
				t = 0;
			}else if(vt[i].first>0){
				t = vt[i].first/x;
			}else{
				t = vt[i].first / x - (((vt[i].first/x) * x ==vt[i].first)?0:1);
			}
		}
		vt[i].first -= x * t;
		vt[i].second -= y * t;
		//cout<<"a "<<vt[i].first<<" "<<vt[i].second<<" "<<t<<endl;
		mp[vt[i]].pb(t);
		if(vt[i].first==0){
			if(x==0)	continue;
			if(x>0){
				vt[i].first+=x; vt[i].second+=y;
				//cout<<"a "<<vt[i].first<<" "<<vt[i].second<<" "<<t-1<<endl;
				mp[vt[i]].pb(t-1);
			}else{
				vt[i].first-=x; vt[i].second-=y;
				//cout<<"a "<<vt[i].first<<" "<<vt[i].second<<" "<<t+1<<endl;
				mp[vt[i]].pb(t+1);
			}
		}
	}
	//cout<<"**"<<endl;
	for(map<pii, vector<int> >::iterator it = mp.begin(); it!=mp.end(); it++){
		tmp = it->second;
		sort(tmp.begin(), tmp.end());
		mp[it->first] = tmp;
	}
	for(map<pii, vector<int> >::iterator it = mp.begin(); it!=mp.end(); it++){
		pii p = it->first;
		//if(p.first==x)	continue;
		//cout<<"+"<<p.first<<" "<<p.second<<endl;
		//if(x==0){
			if(mp.find({(p.first+1), p.second})==mp.end() || mp.find({p.first, p.second+1})==mp.end() || mp.find({(p.first+1), p.second+1})==mp.end())	continue;
			mrg.clear(); mrg2.clear();
			//cout<<p.first<<" "<<p.second<<endl;
			mrg.pb({-INF, INF}); tmp = mp[p]; merge();
			tmp = mp[{p.first+1, p.second}]; merge();
			tmp = mp[{p.first, p.second+1}]; merge();
			tmp = mp[{p.first+1, p.second+1}]; merge();
			if(x==0){
				if(!mrg.empty()){
					ans++;
				}
				continue;
			}
			for(int i=0; i<mrg.size(); i++){
				ans += mrg[i].second - mrg[i].first + 1;
				//cout<<'*'<<mrg[i].first<<" "<<mrg[i].second<<endl;
			}
		/*}else{
			if(mp.find({p.first+1, p.second})==mp.end() || mp.find({p.first, p.second+1})==mp.end() || mp.find({p.first+1, p.second+1})==mp.end())	continue;
			mrg.clear(); mrg2.clear();
			mrg.pb({1, K}); tmp = mp[p]; merge();
			tmp = mp[{(p.first+1)%x, p.second}]; merge();
			tmp = mp[{p.first, p.second+1}]; merge();
			tmp = mp[{(p.first+1)%x, p.second+1}]; merge();
			for(int i=0; i<mrg.size(); i++){
				ans += mrg[i].second - mrg[i].first;
				cout<<'*'<<mrg[i].first<<" "<<mrg[i].second<<endl;
			}
		}*/
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

2016_ho_t4.cpp: In function 'void merge()':
2016_ho_t4.cpp:42:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<tmp.size(); i++){
               ~^~~~~~~~~~~
2016_ho_t4.cpp:71:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i1>=mrg.size()){
        ~~^~~~~~~~~~~~
2016_ho_t4.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i2+1<mrg2.size() && mrg2[i2+1].first<=mrg2[i2].second){
           ~~~~^~~~~~~~~~~~
2016_ho_t4.cpp:92:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i2>=mrg2.size()){
        ~~^~~~~~~~~~~~~
2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:139:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<vt.size(); i++){
                ~^~~~~~~~~~
2016_ho_t4.cpp:144:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
2016_ho_t4.cpp:207:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0; i<mrg.size(); i++){
                 ~^~~~~~~~~~~
2016_ho_t4.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~

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