#include<bits/stdc++.h>
using namespace std;
#define int long long
#define B s[i]
#define A s[l]
struct seg{
int x1,x2,y1,y2,d=0;
}s[1<<17];
int t[1<<17],n,x,y,l,r,cnt,cur=1e18;
map<int,int>mp;
void upd(int x,int v){
for(;x<=cnt;x+=x&-x)
t[x]+=v;
}
int Q(int x){
int v=0;
for(;x;x-=x&-x)
v+=t[x];
return v;
}
bool inter(int n){
priority_queue<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<>>pq;
memset(t,0,sizeof t);
for(int i=1;i<=n;i++)
if(B.x1-B.x2)
pq.push({min(B.x1,B.x2),-1,mp[B.y1],0}),
pq.push({max(B.x2,B.x1),1,mp[B.y1],0});
else pq.push({B.x1,0,mp[min(B.y1,B.y2)],mp[max(B.y2,B.y1)]});
while(pq.size()){
auto[a,b,c,d]=pq.top();
pq.pop();
if(pq.size()&&!b&&!get<1>(pq.top())&&a==get<0>(pq.top()))
if(d>=get<2>(pq.top())) return 1;
if(b<0)
if(Q(c)-Q(c-1))
return 1;
else upd(c,1);
else if(b)
upd(c,-1);
else if((Q(max(d,c))-Q(min(d,c)-1)))
return 1;
}
return 0;
}
bool Inter(seg a, seg b){
if(b.x1>b.x2)swap(b.x1,b.x2);
if(b.y1>b.y2)swap(b.y1,b.y2);
if(a.x1-a.x2)
if(b.x1-b.x2)
return a.y1==b.y1&&max(a.x1,b.x1)<=min(a.x2,b.x2);
else
return a.x1<=b.x1&&b.x1<=a.x2&&b.y1<=a.y1&&a.y1<=b.y2;
else
if(b.x1-b.x2)
return b.x1<=a.x1&&a.x1<=b.x2&&a.y1<=b.y1&&b.y1<=a.y2;
else
return a.x1==b.x1&&max(a.y1,b.y1)<=min(a.y2,b.y2);
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n;r=n;
for(int i=1,d;i<=n;i++){
char c;
cin>>c>>d;
B={x,x,y,y,d+s[i-1].d};
(c-'L'&&c-'R'?B.y2:B.x2)+=(c-'U'&&c-'R'?-1:1)*d;
(c-'L'&&c-'R'?B.y1:B.x1)+=!!(i-1)*(c-'U'&&c-'R'?-1:1);
mp[y=B.y2],x=B.x2,mp[B.y1];
}
for(auto&[i,j]:mp)
j=++cnt;
if(!inter(n))
cout<<s[n].d,exit(0);
while(l<r){
int mid=l+r>>1;
if(inter(mid))
r=mid;
else l=mid+1;
}
for(int i=1;i<l;i++){
if(B.x1>B.x2)swap(B.x1,B.x2);
if(B.y1>B.y2)swap(B.y1,B.y2);
if(!Inter(B,A))
continue;
if(B.x1-B.x2)
if(A.x1-A.x2)
cur=min(cur,(B.x1<=A.x1&&A.x1<=B.x2?0:min(abs(A.x1-B.x1),abs(A.x1-B.x2))));
else
cur=min(cur,abs(B.y1-A.y1));
else
if(A.x1-A.x2)
cur=min(cur,abs(B.x1-A.x1));
else
cur=min(cur,(B.y1<=A.y1&&A.y1<=B.y2?0:min(abs(A.y1-B.y1),abs(B.y1-A.y2))));
}
cout<<cur+1+s[l-1].d;
}
Compilation message
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:75:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
76 ms |
47528 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
23704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
