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