結果

問題 No.596 郵便配達
ユーザー NekosyndromeNekosyndrome
提出日時 2017-11-10 23:53:30
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,634 bytes
コンパイル時間 1,388 ms
コンパイル使用メモリ 159,024 KB
実行使用メモリ 113,156 KB
最終ジャッジ日時 2024-05-03 14:53:29
合計ジャッジ時間 4,224 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 3 ms
9,676 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 3 ms
9,800 KB
testcase_11 AC 3 ms
9,808 KB
testcase_12 AC 3 ms
9,676 KB
testcase_13 WA -
testcase_14 AC 3 ms
9,676 KB
testcase_15 AC 2 ms
9,676 KB
testcase_16 AC 3 ms
9,804 KB
testcase_17 AC 3 ms
9,932 KB
testcase_18 WA -
testcase_19 AC 3 ms
9,676 KB
testcase_20 AC 312 ms
113,032 KB
testcase_21 AC 311 ms
113,156 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 ll[M],rr[M];
void init()
{
	REP(i,1,n) mnp[i]=INF, mxp[i]=-INF;
	REP(i,1,m)
	{
		int x,d,y;
		RI(x,d);
		while(d--)
		{
			RI(y);
			if(y<=x) mnp[x] = min(mnp[x], y);
			if(y>=x) 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) ll[i] = mnp[i];
		else ll[i] = min(ll[i+1], mnp[i]);
	}

	REP(i,st,ed)
	{
		if(i==st) rr[i] = mxp[i];
		else rr[i] = max(rr[i-1], mxp[i]);
	}
	
	//rl
	//re = min(re, ed-st + max(ed-ll[st], 0));

	//lr
	//re = min(re, ed-st + max(rr[ed]-st, 0));

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

	//rlr
	REP(i,st,ed)
	{
		int rrr = max(ed, rr[i]);
		int lll = min(st, ll[st]);
		int tmp = (rrr-i) + (rrr-lll);
		if(i-1>=st) tmp += max(rr[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