結果

問題 No.596 郵便配達
ユーザー NekosyndromeNekosyndrome
提出日時 2017-11-11 00:05:19
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,730 bytes
コンパイル時間 1,324 ms
コンパイル使用メモリ 158,724 KB
実行使用メモリ 167,808 KB
最終ジャッジ日時 2024-05-03 14:57:19
合計ジャッジ時間 4,201 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 WA -
testcase_21 AC 334 ms
167,680 KB
testcase_22 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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);
	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 = llfr[i];
		int rrr = rrbk[st];
		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 = rrbk[i];
		int lll = llfr[ed];
		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