Submission #2077670


Source Code Expand

#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 Info

Submission Time
Task D - Squares, Pieces and Coloring
User leafmoon
Language C++14 (Clang 3.8.0)
Score 100
Code Size 1261 Byte
Status AC
Exec Time 1535 ms
Memory 2816 KB

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3
Score / Max Score 0 / 0 35 / 35 40 / 40 25 / 25
Status
AC × 3
AC × 11
AC × 15
AC × 39
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
Dataset1 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 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 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
Case Name Status Exec Time Memory
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