Submission #1771703
Source Code Expand
#include<bits/stdc++.h>
#define N 100005
#define x first
#define y second
#define mp(x,y) make_pair(x,y)
using namespace std;
deque<pair<int,long long> > dq;
int k,x,m,rx[N];
int main(){
scanf("%d%d",&x,&k);
for(int i=1;i<=k;i++) scanf("%d",&rx[i]);
scanf("%d",&m);
dq.push_back(mp(0,0LL));dq.push_back(mp(x,x*1LL));
long long add = 0;int pos=0;
while(m--){
int t,a;scanf("%d%d",&t,&a);
while(pos<k&&t>rx[pos+1]){
pos++;
add += (pos%2==1) ? rx[pos-1]-rx[pos]:rx[pos]-rx[pos-1];
while(!dq.empty()&&dq.front().y+add <= 0) dq.pop_front();
if(dq.empty()) dq.push_back(mp(0,-add)),dq.push_back(mp(x,-add));
else if(!dq.empty()&&dq.front().x > dq.front().y+add)
dq.push_front(mp(dq.front().x - (dq.front().y+add),-add));
if(dq.front().x!=0) dq.push_front(mp(0,-add));
while(!dq.empty()&&dq.back().y+add >= x) dq.pop_back();
if(dq.empty()) dq.push_back(mp(0,x-add)),dq.push_back(mp(x,x-add));
else if(!dq.empty()&&dq.back().x + x - (dq.back().y+add) <x)
dq.push_back(mp(dq.back().x + x - (dq.back().y+add),x-add));
if(dq.back().x!=x) dq.push_back(mp(x,x-add));
}
long long now=0;
int l=0,r=dq.size();
while(l+1<r){
int mid=(l+r)>>1;
if(dq[mid].x <= a) l=mid;
else r = mid;
}
if(dq[l].x==a) now=dq[l].y+add;
else now=dq[l].y+ add + (dq[l+1].y-dq[l].y)/(dq[l+1].x-dq[l].x)*(a-dq[l].x);
if(pos%2==1) now+=t-rx[pos];
else now-=t-rx[pos];
printf("%lld\n",min(max(0LL,now),x*1LL));
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Sandglass |
User |
Wuvin |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
1793 Byte |
Status |
AC |
Exec Time |
50 ms |
Memory |
1536 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:11:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&k);
^
./Main.cpp:12:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=k;i++) scanf("%d",&rx[i]);
^
./Main.cpp:13:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&m);
^
./Main.cpp:17:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int t,a;scanf("%d%d",&t,&a);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_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, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
1 ms |
256 KB |
0_001.txt |
AC |
1 ms |
256 KB |
0_002.txt |
AC |
1 ms |
256 KB |
1_003.txt |
AC |
39 ms |
768 KB |
1_004.txt |
AC |
41 ms |
768 KB |
1_005.txt |
AC |
43 ms |
768 KB |
1_006.txt |
AC |
39 ms |
896 KB |
1_007.txt |
AC |
42 ms |
896 KB |
1_008.txt |
AC |
44 ms |
896 KB |
1_009.txt |
AC |
42 ms |
896 KB |
1_010.txt |
AC |
42 ms |
896 KB |
1_011.txt |
AC |
45 ms |
896 KB |
1_012.txt |
AC |
41 ms |
1024 KB |
1_013.txt |
AC |
42 ms |
1024 KB |
1_014.txt |
AC |
45 ms |
1024 KB |
1_015.txt |
AC |
42 ms |
1152 KB |
1_016.txt |
AC |
43 ms |
1152 KB |
1_017.txt |
AC |
46 ms |
1024 KB |
1_018.txt |
AC |
43 ms |
1152 KB |
1_019.txt |
AC |
45 ms |
1152 KB |
1_020.txt |
AC |
46 ms |
1152 KB |
1_021.txt |
AC |
43 ms |
1152 KB |
1_022.txt |
AC |
45 ms |
1280 KB |
1_023.txt |
AC |
47 ms |
1280 KB |
1_024.txt |
AC |
43 ms |
1152 KB |
1_025.txt |
AC |
46 ms |
1408 KB |
1_026.txt |
AC |
48 ms |
1408 KB |
1_027.txt |
AC |
44 ms |
1152 KB |
1_028.txt |
AC |
45 ms |
1280 KB |
1_029.txt |
AC |
49 ms |
1536 KB |
1_030.txt |
AC |
46 ms |
1152 KB |
1_031.txt |
AC |
46 ms |
1280 KB |
1_032.txt |
AC |
50 ms |
1536 KB |
1_033.txt |
AC |
34 ms |
1024 KB |
1_034.txt |
AC |
34 ms |
1024 KB |
1_035.txt |
AC |
46 ms |
1408 KB |
1_036.txt |
AC |
35 ms |
1152 KB |
1_037.txt |
AC |
36 ms |
1152 KB |
1_038.txt |
AC |
49 ms |
1536 KB |
1_039.txt |
AC |
35 ms |
896 KB |
1_040.txt |
AC |
37 ms |
1280 KB |
1_041.txt |
AC |
50 ms |
1536 KB |