Submission #944866

#	Time	Username	Problem	Language	Result	Execution time	Memory
944866		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	78 ms	47528 KiB

sortbooks

#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 (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:75:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         int mid=l+r>>1;
      |                 ~^~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23