AtCoder Regular Contest 070

Submission #1356873

Source codeソースコード

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <utility>
typedef long long ll;

const int maxn = 100010;

std::multiset<ll> inc,dec;
std::multiset<ll>::iterator iter;
ll l[maxn], r[maxn], len[maxn];

int main()
{
	//freopen("E.in","r",stdin);
	int n;
	scanf("%d",&n);
	
	ll offset_dec = 0, offset_inc  = 0, ans = 0;
	scanf("%lld%lld",&l[1], &r[1]);
	dec.insert(r[1]); inc.insert(r[1]); len[1] = r[1] - l[1];
	
	for (int i=2;i<=n;i++)
	{
		scanf("%lld%lld",&l[i],&r[i]);
		len[i] = r[i] - l[i];
		
		//parallel move to both sides
		offset_dec -= len[i-1];
		offset_inc += len[i];
		
		// + |x-Ri|
		if (r[i] >= *inc.begin() + offset_inc)
		{
			ans += r[i] - (*inc.begin() + offset_inc);
			dec.insert(*inc.begin() + offset_inc - offset_dec);
			inc.erase(inc.begin());
			inc.insert(r[i] - offset_inc);
			inc.insert(r[i] - offset_inc);
		}
		else if (r[i] <= *(dec.rbegin()) + offset_dec)
		{
			ans += (*dec.rbegin() + offset_dec) - r[i];
			inc.insert(*dec.rbegin() + offset_dec - offset_inc);
			iter = dec.end();
			iter--;
			dec.erase(iter);
			dec.insert(r[i] - offset_dec);
			dec.insert(r[i] - offset_dec);
		}
		else
		{
			dec.insert(r[i] - offset_dec);
			inc.insert(r[i] - offset_inc);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Submission

Task問題 E - NarrowRectangles
User nameユーザ名 Gabriel
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1000
Source lengthソースコード長 1337 Byte
File nameファイル名
Exec time実行時間 94 ms
Memory usageメモリ使用量 11904 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:18:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:21:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&l[1], &r[1]);
^
./Main.cpp:26:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&l[i],&r[i]);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_000.txt,0_001.txt,0_002.txt,0_003.txt,0_004.txt
Subtask 300 / 300 0_000,0_001,0_004,1_005.txt,1_006.txt,1_007.txt,1_008.txt,1_009.txt,1_010.txt,1_011.txt,1_012.txt,1_013.txt,1_014.txt,1_015.txt,1_016.txt,1_017.txt
All 700 / 700 0_000.txt,0_001.txt,0_002.txt,0_003.txt,0_004.txt,1_005.txt,1_006.txt,1_007.txt,1_008.txt,1_009.txt,1_010.txt,1_011.txt,1_012.txt,1_013.txt,1_014.txt,1_015.txt,1_016.txt,1_017.txt,2_018.txt,2_019.txt,2_020.txt,2_021.txt,2_022.txt,2_023.txt,2_024.txt,2_025.txt,2_026.txt,2_027.txt,2_028.txt,2_029.txt,2_030.txt,2_031.txt,2_032.txt,2_033.txt,2_034.txt,2_035.txt,2_036.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_000.txt AC 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
0_003.txt AC 1 ms 256 KB
0_004.txt AC 1 ms 256 KB
1_005.txt AC 1 ms 256 KB
1_006.txt AC 1 ms 256 KB
1_007.txt AC 1 ms 256 KB
1_008.txt AC 1 ms 256 KB
1_009.txt AC 1 ms 256 KB
1_010.txt AC 1 ms 256 KB
1_011.txt AC 1 ms 256 KB
1_012.txt AC 1 ms 256 KB
1_013.txt AC 1 ms 256 KB
1_014.txt AC 1 ms 256 KB
1_015.txt AC 1 ms 256 KB
1_016.txt AC 1 ms 256 KB
1_017.txt AC 1 ms 256 KB
2_018.txt AC 82 ms 11904 KB
2_019.txt AC 74 ms 11904 KB
2_020.txt AC 65 ms 11904 KB
2_021.txt AC 57 ms 11904 KB
2_022.txt AC 57 ms 11904 KB
2_023.txt AC 56 ms 11904 KB
2_024.txt AC 56 ms 11904 KB
2_025.txt AC 59 ms 11904 KB
2_026.txt AC 55 ms 11904 KB
2_027.txt AC 57 ms 11904 KB
2_028.txt AC 56 ms 11904 KB
2_029.txt AC 56 ms 11904 KB
2_030.txt AC 56 ms 11904 KB
2_031.txt AC 90 ms 11904 KB
2_032.txt AC 91 ms 11904 KB
2_033.txt AC 94 ms 11904 KB
2_034.txt AC 89 ms 11904 KB
2_035.txt AC 64 ms 11904 KB
2_036.txt AC 68 ms 11904 KB