CODE FESTIVAL 2015 予選B

Submission #2077670

Source codeソースコード

#include <cstdio>
#include <deque>
#include <algorithm>
using namespace std;
typedef pair<long long,long long> pll;
 
int main(){
	long long l,v,r;
	deque<pll> se;
	for(scanf("%lld",&l);~scanf("%lld%lld",&l,&v);){
		r=l+v-1;
		auto right=lower_bound(se.begin(),se.end(),make_pair(l,0LL)); //l <= se[right_idx].first
		size_t right_idx=right-se.begin();
		for(;l<=r;){
			long long consumed=0;
			if(right_idx!=0){
				size_t left_idx=right_idx-1;
				if(l<=se[left_idx].second+1){ // overlap with left
					consumed-=se[left_idx].second - se[left_idx].first + 1;
					l=se[left_idx].first;
					r=max(r,se[left_idx].second);
					//result-=se[left_idx].second-se[left_idx].first+1;
					se.erase(se.begin()+left_idx);
					right_idx--;
				}
			}
			while(right_idx<se.size() && se[right_idx].first<=r){ // overlap with right
				consumed-=se[right_idx].second - se[right_idx].first + 1;
				r=max(r,se[right_idx].second);
				//result-=se[right_idx].second-se[right_idx].first+1;
				se.erase(se.begin()+right_idx);
			}
			//result+=r-l+1;
			//result2+=r-l+1;
			consumed+=r-l+1;
			se.insert(se.begin()+right_idx,make_pair(l,r));
			right_idx++;
			v-=consumed;
			l=r+1;
			r=l+v-1;
		}
		printf("%lld\n",r);
	}
}

Submission

Task問題 D - マスと駒と色塗り/Squares, Pieces and Coloring
User nameユーザ名 cf16::002_ciel
Created time投稿日時
Language言語 C++14 (Clang 3.8.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 1261 Byte
File nameファイル名
Exec time実行時間 1535 ms
Memory usageメモリ使用量 2816 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample-01.txt,sample-02.txt,sample-03.txt
Dataset1 35 / 35 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt
Dataset2 40 / 40 sample-01.txt,sample-02.txt,sample-03.txt,02-01.txt,02-02.txt,02-03.txt,02-04.txt,02-05.txt,02-06.txt,02-07.txt,02-08.txt,02-09.txt,02-10.txt,02-11.txt,02-12.txt
Dataset3 25 / 25 sample-01.txt,sample-02.txt,sample-03.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,02-01.txt,02-02.txt,02-03.txt,02-04.txt,02-05.txt,02-06.txt,02-07.txt,02-08.txt,02-09.txt,02-10.txt,02-11.txt,02-12.txt,03-01.txt,03-02.txt,03-03.txt,03-04.txt,03-05.txt,03-06.txt,03-07.txt,03-08.txt,03-09.txt,03-10.txt,03-11.txt,03-12.txt,sample-01.txt,sample-02.txt,sample-03.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 17 ms 512 KB
01-02.txt AC 31 ms 896 KB
01-03.txt AC 209 ms 1024 KB
01-04.txt AC 363 ms 1280 KB
01-05.txt AC 1 ms 256 KB
01-06.txt AC 1 ms 256 KB
01-07.txt AC 1 ms 256 KB
01-08.txt AC 5 ms 384 KB
01-09.txt AC 266 ms 896 KB
02-01.txt AC 2 ms 256 KB
02-02.txt AC 2 ms 256 KB
02-03.txt AC 2 ms 256 KB
02-04.txt AC 1 ms 256 KB
02-05.txt AC 2 ms 256 KB
02-06.txt AC 2 ms 256 KB
02-07.txt AC 2 ms 256 KB
02-08.txt AC 2 ms 256 KB
02-09.txt AC 2 ms 256 KB
02-10.txt AC 1 ms 256 KB
02-11.txt AC 1 ms 256 KB
02-12.txt AC 2 ms 256 KB
03-01.txt AC 43 ms 1664 KB
03-02.txt AC 43 ms 1664 KB
03-03.txt AC 43 ms 1792 KB
03-04.txt AC 31 ms 896 KB
03-05.txt AC 1524 ms 2816 KB
03-06.txt AC 42 ms 1792 KB
03-07.txt AC 42 ms 1664 KB
03-08.txt AC 1535 ms 2816 KB
03-09.txt AC 1494 ms 2816 KB
03-10.txt AC 6 ms 384 KB
03-11.txt AC 42 ms 1664 KB
03-12.txt AC 42 ms 1664 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB