Submission #549169
Source Code Expand
#include <cstdio> #include <set> using namespace std; typedef pair<long long,long long> pll; int main(){ long long l,v,r; set<pll> se; for(scanf("%lld",&l);~scanf("%lld%lld",&l,&v);){ r=l+v-1; auto right=se.lower_bound(make_pair(l,0LL)); //p.first <= right.first for(;l<=r;){ long long consumed=0; if(right!=se.begin()){ --right; auto left=right; ++right; if(l<=left->second+1){ // overlap with left (範囲を+1することで左に接しているのもマージ) consumed-=left->second - left->first + 1; l=left->first; r=max(r,left->second); //result-=left->second-left->first+1; se.erase(left); } } while(right!=se.end() && right->first<=r){ // overlap with right consumed-=right->second - right->first + 1; r=max(r,right->second); //result-=right->second-right->first+1; se.erase(right++); } //result+=r-l+1; //result2+=r-l+1; consumed+=r-l+1; se.insert(right,make_pair(l,r)); 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++11 (GCC 4.9.2) |
Score | 100 |
Code Size | 1089 Byte |
Status | AC |
Exec Time | 157 ms |
Memory | 7024 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:9:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] for(scanf("%lld",&l);~scanf("%lld%lld",&l,&v);){ ^
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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 60 ms | 800 KB |
01-02.txt | AC | 90 ms | 676 KB |
01-03.txt | AC | 112 ms | 1608 KB |
01-04.txt | AC | 81 ms | 3920 KB |
01-05.txt | AC | 25 ms | 800 KB |
01-06.txt | AC | 25 ms | 800 KB |
01-07.txt | AC | 27 ms | 916 KB |
01-08.txt | AC | 34 ms | 800 KB |
01-09.txt | AC | 91 ms | 1752 KB |
02-01.txt | AC | 25 ms | 792 KB |
02-02.txt | AC | 26 ms | 916 KB |
02-03.txt | AC | 26 ms | 800 KB |
02-04.txt | AC | 26 ms | 700 KB |
02-05.txt | AC | 25 ms | 796 KB |
02-06.txt | AC | 25 ms | 800 KB |
02-07.txt | AC | 25 ms | 916 KB |
02-08.txt | AC | 26 ms | 928 KB |
02-09.txt | AC | 25 ms | 832 KB |
02-10.txt | AC | 25 ms | 924 KB |
02-11.txt | AC | 25 ms | 800 KB |
02-12.txt | AC | 25 ms | 804 KB |
03-01.txt | AC | 115 ms | 796 KB |
03-02.txt | AC | 115 ms | 920 KB |
03-03.txt | AC | 111 ms | 668 KB |
03-04.txt | AC | 97 ms | 796 KB |
03-05.txt | AC | 148 ms | 7024 KB |
03-06.txt | AC | 113 ms | 672 KB |
03-07.txt | AC | 113 ms | 672 KB |
03-08.txt | AC | 153 ms | 6964 KB |
03-09.txt | AC | 157 ms | 6964 KB |
03-10.txt | AC | 34 ms | 672 KB |
03-11.txt | AC | 113 ms | 796 KB |
03-12.txt | AC | 147 ms | 924 KB |
sample-01.txt | AC | 25 ms | 924 KB |
sample-02.txt | AC | 24 ms | 800 KB |
sample-03.txt | AC | 25 ms | 736 KB |