結果

問題 No.596 郵便配達
コンテスト
ユーザー Nekosyndrome
提出日時 2017-11-11 00:15:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,843 bytes
コンパイル時間 1,846 ms
コンパイル使用メモリ 159,212 KB
実行使用メモリ 167,680 KB
最終ジャッジ日時 2024-11-24 16:07:29
合計ジャッジ時間 4,024 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15 WA * 8
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void RI(int&, T& ...) [with T = {int}]’:
main.cpp:16:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   16 |     scanf("%d",&head);
      |     ~~~~~^~~~~~~~~~~~
main.cpp: In function ‘void RI(int&, T& ...) [with T = {}]’:
main.cpp:16:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]

ソースコード

diff # 

#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define FORD(x,y,z) for(int x=y;x>=z;x--)
#define MSET(x,y) memset(x,y,sizeof(x))
#define FOR(x,y) for(__typeof(y.begin()) x=y.begin();x!=y.end();x++)
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define SZ size()
#define M 7000005
#define INF 1000000000
void RI(){}
template<typename... T>
void RI( int& head, T&... tail ) {
    scanf("%d",&head);
    RI(tail...);
}
using namespace std;
typedef long long LL;
int n,m,st,ed;
int mnp[M],mxp[M];
int llfr[M],rrfr[M],llbk[M],rrbk[M];
void init()
{
	REP(i,1,n) mnp[i]=INF, mxp[i]=-INF;
	REP(i,1,m)
	{
		int x,d,y;
		RI(x,d);
		if(mnp[x]==INF)
		{
			mnp[x] = x;
			mxp[x] = x;
		}
		while(d--)
		{
			RI(y);
			mnp[x] = min(mnp[x], y);
			mxp[x] = max(mxp[x], y);
		}
	}

	st=0, ed=n-1;
	while(st<n && mnp[st]==INF) st++;
	while(ed>=0 && mnp[ed]==INF) ed--;
}
int calc()
{
	int re = (n-1)+(n-1);
	REP(i,st,ed)
	{
		if(mnp[i]==i) mnp[i]=INF;
		if(mxp[i]==i) mxp[i]=-INF;
	}
	FORD(i,ed,st)
	{
		if(i==ed) {
			llbk[i] = mnp[i];
			rrbk[i] = mxp[i];
		}
		else {
			llbk[i] = min(llbk[i+1], mnp[i]);
			rrbk[i] = max(rrbk[i+1], mxp[i]);
		}
	}

	REP(i,st,ed)
	{
		if(i==st) {
			rrfr[i] = mxp[i];
			llfr[i] = mnp[i];
		}
		else {
			rrfr[i] = max(rrfr[i-1], mxp[i]);
			llfr[i] = min(llfr[i-1], mnp[i]);
		}
	}

	//lrl
	REP(i,st,ed)
	{
		int lll = min(llfr[i], st);
		int rrr = max(rrbk[st], ed);
		int tmp = (i-lll) + (rrr-lll);
		if(i+1<=ed) tmp += max(rrr-llbk[i+1], 0);
		re = min(re, tmp);
	}

	//rlr
	REP(i,st,ed)
	{
		int rrr = max(rrbk[i], ed);
		int lll = min(llfr[ed], st);
		int tmp = (rrr-i) + (rrr-lll);
		if(i-1>=st) tmp += max(rrfr[i-1]-lll, 0);
		re = min(re, tmp);
	}
	return re;
}
int main()
{
	while(~scanf("%d %d",&n,&m))
	{
		init();
		
		printf("%d\n",calc());
		
	}
	return 0;
}
0