oj.uz

Submission #1075074

# Submission time Handle Problem Language Result Execution time Memory
1075074 2024-08-25T18:05:25 Z amirhoseinfar1385 Shortcut (IOI16_shortcut) C++17
0 / 100
 10 ms 4720 KB 
#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,lg=17,kaf=(1<<lg);
long long inf=1e16,n,c,inf2=2e9+5;
long long all[maxn],alld[maxn],ps[maxn],l1,l2,r1,r2;

struct segmentmn{
    int seg[(1<<(lg+1))];
    segmentmn(){
        for(int i=0;i<kaf*2;i++){
            seg[i]=inf2;
        }
    }
    void clear(){
        for(int i=0;i<kaf*2;i++){
            seg[i]=inf2;
        }
    }
    void upd(int i,int w){
        i+=kaf;
        seg[i]=w;
        i>>=1;
        while(i>0){
            seg[i]=min(seg[(i<<1)],seg[(i<<1)^1]);
            i>>=1;
        }
    }
    int pors(int i,int l,int r,int tl,int tr){
        if(l>r||l>tr||r<tl||tl>tr){
            return inf2;
        }
        if(l>=tl&&r<=tr){
            return seg[i];
        }
        int m=(l+r)>>1;
        return min(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
    }
}segmn;
 
struct segmentmx{
    int seg[(1<<(lg+1))];
    segmentmx(){
        for(int i=0;i<kaf*2;i++){
            seg[i]=-inf2;
        }
    }
    void clear(){
        for(int i=0;i<kaf*2;i++){
            seg[i]=-inf2;
        }
    }
    void upd(int i,int w){
        i+=kaf;
        seg[i]=w;
        i>>=1;
        while(i>0){
            seg[i]=max(seg[(i<<1)],seg[(i<<1)^1]);
            i>>=1;
        }
    }
    int pors(int i,int l,int r,int tl,int tr){
        if(l>r||l>tr||r<tl||tl>tr){
            return -inf;
        }
        if(l>=tl&&r<=tr){
            return seg[i];
        }
        int m=(l+r)>>1;
        return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
    }
}segmx;

void addr(long long x1,long long y1,long long x2,long long y2){
    long long fx=x1+y1;
    long long fy=x1-y1;
    x1=fx;
    y1=fy;
    fx=x2+y2;
    fy=x2-y2;
    x2=fx;
    y2=fy;
    l1=max(l1,x1);
    l2=min(l2,x2);
    r1=max(r1,y2);
    r2=min(r2,y1);
}

bool dakh(long long x,long long y){
    long long fx=x+y;
    long long fy=x-y;
    x=fx;
    y=fy;
    if(x>=l1&&x<=l2&&y>=r1&&y<=r2){
        return 1;
    }
    return 0;
}

bool check(long long mid){
    l1=r1=-inf;
    l2=r2=inf;
    segmx.clear();
    segmn.clear();
    vector<pair<long long,int>>allv;
    int av=n+1;
    for(int i=1;i<=n;i++){
        allv.push_back(make_pair(-ps[i]+alld[i],-i));
        allv.push_back(make_pair(mid-ps[i]-alld[i],i));
    }
    sort(allv.begin(),allv.end());
    while((int)allv.size()>0){
        auto x=allv.back();
        allv.pop_back();
        if(x.second<0){
            segmx.upd(-x.second,alld[-x.second]+ps[-x.second]);
            segmn.upd(-x.second,-alld[-x.second]+ps[-x.second]);
            av=min(av,-x.second);
        }
        else{
            if(av<x.second)
                addr(ps[x.second],-mid+c+alld[x.second]+segmx.pors(1,0,kaf-1,0,x.second-1),ps[x.second],mid-c-alld[x.second]+segmn.pors(1,0,kaf-1,0,x.second-1));
        }
    }
    vector<long long>vl;
    for(long long i=1;i<=n;i++){
        vl.push_back(ps[i]);
        long long l=0,r=ps[n];
        l=max(l,l1-ps[i]);
        r=min(r,l2-ps[i]);
        l=max(l,-r2+ps[i]);
        r=min(r,-r1+ps[i]);
        if(r>=l){
            if(vl.back()>=l){
                int p=lower_bound(vl.begin(),vl.end(),l)-vl.begin();
                if(vl[p]<=r){
                    return 1;
                }
            }
        }
    }
    return 0;
}

long long find_shortcut(int n_, std::vector<int> l, std::vector<int> d,int c_)
{
    n=n_;
    c=c_;
    alld[1]=d[0];
    for(long long i=2;i<=n;i++){
        all[i]=l[i-2];
        ps[i]=all[i]+ps[i-1];
        alld[i]=d[i-1];
    }
    long long low=-1,high=inf,mid;
    while(high-low>1){
        mid=(high+low)>>1;
        if(check(mid)){
            high=mid;
        }else{
            low=mid;
        }
    }
    return high;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4700 KB n = 4, 80 is a correct answer
2 Correct 10 ms 4720 KB n = 9, 110 is a correct answer
3 Correct 10 ms 4700 KB n = 4, 21 is a correct answer
4 Correct 10 ms 2680 KB n = 3, 4 is a correct answer
5 Correct 10 ms 2676 KB n = 2, 62 is a correct answer
6 Correct 10 ms 4700 KB n = 2, 3 is a correct answer
7 Correct 10 ms 2676 KB n = 3, 29 is a correct answer
8 Correct 10 ms 4716 KB n = 2, 3 is a correct answer
9 Correct 10 ms 4696 KB n = 2, 3 is a correct answer
10 Correct 10 ms 2652 KB n = 2, 2000000001 is a correct answer
11 Correct 10 ms 4700 KB n = 2, 3000000000 is a correct answer
12 Correct 10 ms 2652 KB n = 3, 3000000000 is a correct answer
13 Correct 10 ms 4716 KB n = 3, 3000000000 is a correct answer
14 Correct 10 ms 2648 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 2652 KB n = 4, 4000000000 is a correct answer
16 Correct 10 ms 2680 KB n = 5, 4000000000 is a correct answer
17 Correct 10 ms 4700 KB n = 10, 1000000343 is a correct answer
18 Correct 10 ms 2652 KB n = 10, 3189 is a correct answer
19 Incorrect 10 ms 2652 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4700 KB n = 4, 80 is a correct answer
2 Correct 10 ms 4720 KB n = 9, 110 is a correct answer
3 Correct 10 ms 4700 KB n = 4, 21 is a correct answer
4 Correct 10 ms 2680 KB n = 3, 4 is a correct answer
5 Correct 10 ms 2676 KB n = 2, 62 is a correct answer
6 Correct 10 ms 4700 KB n = 2, 3 is a correct answer
7 Correct 10 ms 2676 KB n = 3, 29 is a correct answer
8 Correct 10 ms 4716 KB n = 2, 3 is a correct answer
9 Correct 10 ms 4696 KB n = 2, 3 is a correct answer
10 Correct 10 ms 2652 KB n = 2, 2000000001 is a correct answer
11 Correct 10 ms 4700 KB n = 2, 3000000000 is a correct answer
12 Correct 10 ms 2652 KB n = 3, 3000000000 is a correct answer
13 Correct 10 ms 4716 KB n = 3, 3000000000 is a correct answer
14 Correct 10 ms 2648 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 2652 KB n = 4, 4000000000 is a correct answer
16 Correct 10 ms 2680 KB n = 5, 4000000000 is a correct answer
17 Correct 10 ms 4700 KB n = 10, 1000000343 is a correct answer
18 Correct 10 ms 2652 KB n = 10, 3189 is a correct answer
19 Incorrect 10 ms 2652 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4700 KB n = 4, 80 is a correct answer
2 Correct 10 ms 4720 KB n = 9, 110 is a correct answer
3 Correct 10 ms 4700 KB n = 4, 21 is a correct answer
4 Correct 10 ms 2680 KB n = 3, 4 is a correct answer
5 Correct 10 ms 2676 KB n = 2, 62 is a correct answer
6 Correct 10 ms 4700 KB n = 2, 3 is a correct answer
7 Correct 10 ms 2676 KB n = 3, 29 is a correct answer
8 Correct 10 ms 4716 KB n = 2, 3 is a correct answer
9 Correct 10 ms 4696 KB n = 2, 3 is a correct answer
10 Correct 10 ms 2652 KB n = 2, 2000000001 is a correct answer
11 Correct 10 ms 4700 KB n = 2, 3000000000 is a correct answer
12 Correct 10 ms 2652 KB n = 3, 3000000000 is a correct answer
13 Correct 10 ms 4716 KB n = 3, 3000000000 is a correct answer
14 Correct 10 ms 2648 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 2652 KB n = 4, 4000000000 is a correct answer
16 Correct 10 ms 2680 KB n = 5, 4000000000 is a correct answer
17 Correct 10 ms 4700 KB n = 10, 1000000343 is a correct answer
18 Correct 10 ms 2652 KB n = 10, 3189 is a correct answer
19 Incorrect 10 ms 2652 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4700 KB n = 4, 80 is a correct answer
2 Correct 10 ms 4720 KB n = 9, 110 is a correct answer
3 Correct 10 ms 4700 KB n = 4, 21 is a correct answer
4 Correct 10 ms 2680 KB n = 3, 4 is a correct answer
5 Correct 10 ms 2676 KB n = 2, 62 is a correct answer
6 Correct 10 ms 4700 KB n = 2, 3 is a correct answer
7 Correct 10 ms 2676 KB n = 3, 29 is a correct answer
8 Correct 10 ms 4716 KB n = 2, 3 is a correct answer
9 Correct 10 ms 4696 KB n = 2, 3 is a correct answer
10 Correct 10 ms 2652 KB n = 2, 2000000001 is a correct answer
11 Correct 10 ms 4700 KB n = 2, 3000000000 is a correct answer
12 Correct 10 ms 2652 KB n = 3, 3000000000 is a correct answer
13 Correct 10 ms 4716 KB n = 3, 3000000000 is a correct answer
14 Correct 10 ms 2648 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 2652 KB n = 4, 4000000000 is a correct answer
16 Correct 10 ms 2680 KB n = 5, 4000000000 is a correct answer
17 Correct 10 ms 4700 KB n = 10, 1000000343 is a correct answer
18 Correct 10 ms 2652 KB n = 10, 3189 is a correct answer
19 Incorrect 10 ms 2652 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4700 KB n = 4, 80 is a correct answer
2 Correct 10 ms 4720 KB n = 9, 110 is a correct answer
3 Correct 10 ms 4700 KB n = 4, 21 is a correct answer
4 Correct 10 ms 2680 KB n = 3, 4 is a correct answer
5 Correct 10 ms 2676 KB n = 2, 62 is a correct answer
6 Correct 10 ms 4700 KB n = 2, 3 is a correct answer
7 Correct 10 ms 2676 KB n = 3, 29 is a correct answer
8 Correct 10 ms 4716 KB n = 2, 3 is a correct answer
9 Correct 10 ms 4696 KB n = 2, 3 is a correct answer
10 Correct 10 ms 2652 KB n = 2, 2000000001 is a correct answer
11 Correct 10 ms 4700 KB n = 2, 3000000000 is a correct answer
12 Correct 10 ms 2652 KB n = 3, 3000000000 is a correct answer
13 Correct 10 ms 4716 KB n = 3, 3000000000 is a correct answer
14 Correct 10 ms 2648 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 2652 KB n = 4, 4000000000 is a correct answer
16 Correct 10 ms 2680 KB n = 5, 4000000000 is a correct answer
17 Correct 10 ms 4700 KB n = 10, 1000000343 is a correct answer
18 Correct 10 ms 2652 KB n = 10, 3189 is a correct answer
19 Incorrect 10 ms 2652 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4700 KB n = 4, 80 is a correct answer
2 Correct 10 ms 4720 KB n = 9, 110 is a correct answer
3 Correct 10 ms 4700 KB n = 4, 21 is a correct answer
4 Correct 10 ms 2680 KB n = 3, 4 is a correct answer
5 Correct 10 ms 2676 KB n = 2, 62 is a correct answer
6 Correct 10 ms 4700 KB n = 2, 3 is a correct answer
7 Correct 10 ms 2676 KB n = 3, 29 is a correct answer
8 Correct 10 ms 4716 KB n = 2, 3 is a correct answer
9 Correct 10 ms 4696 KB n = 2, 3 is a correct answer
10 Correct 10 ms 2652 KB n = 2, 2000000001 is a correct answer
11 Correct 10 ms 4700 KB n = 2, 3000000000 is a correct answer
12 Correct 10 ms 2652 KB n = 3, 3000000000 is a correct answer
13 Correct 10 ms 4716 KB n = 3, 3000000000 is a correct answer
14 Correct 10 ms 2648 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 2652 KB n = 4, 4000000000 is a correct answer
16 Correct 10 ms 2680 KB n = 5, 4000000000 is a correct answer
17 Correct 10 ms 4700 KB n = 10, 1000000343 is a correct answer
18 Correct 10 ms 2652 KB n = 10, 3189 is a correct answer
19 Incorrect 10 ms 2652 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4700 KB n = 4, 80 is a correct answer
2 Correct 10 ms 4720 KB n = 9, 110 is a correct answer
3 Correct 10 ms 4700 KB n = 4, 21 is a correct answer
4 Correct 10 ms 2680 KB n = 3, 4 is a correct answer
5 Correct 10 ms 2676 KB n = 2, 62 is a correct answer
6 Correct 10 ms 4700 KB n = 2, 3 is a correct answer
7 Correct 10 ms 2676 KB n = 3, 29 is a correct answer
8 Correct 10 ms 4716 KB n = 2, 3 is a correct answer
9 Correct 10 ms 4696 KB n = 2, 3 is a correct answer
10 Correct 10 ms 2652 KB n = 2, 2000000001 is a correct answer
11 Correct 10 ms 4700 KB n = 2, 3000000000 is a correct answer
12 Correct 10 ms 2652 KB n = 3, 3000000000 is a correct answer
13 Correct 10 ms 4716 KB n = 3, 3000000000 is a correct answer
14 Correct 10 ms 2648 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 2652 KB n = 4, 4000000000 is a correct answer
16 Correct 10 ms 2680 KB n = 5, 4000000000 is a correct answer
17 Correct 10 ms 4700 KB n = 10, 1000000343 is a correct answer
18 Correct 10 ms 2652 KB n = 10, 3189 is a correct answer
19 Incorrect 10 ms 2652 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4700 KB n = 4, 80 is a correct answer
2 Correct 10 ms 4720 KB n = 9, 110 is a correct answer
3 Correct 10 ms 4700 KB n = 4, 21 is a correct answer
4 Correct 10 ms 2680 KB n = 3, 4 is a correct answer
5 Correct 10 ms 2676 KB n = 2, 62 is a correct answer
6 Correct 10 ms 4700 KB n = 2, 3 is a correct answer
7 Correct 10 ms 2676 KB n = 3, 29 is a correct answer
8 Correct 10 ms 4716 KB n = 2, 3 is a correct answer
9 Correct 10 ms 4696 KB n = 2, 3 is a correct answer
10 Correct 10 ms 2652 KB n = 2, 2000000001 is a correct answer
11 Correct 10 ms 4700 KB n = 2, 3000000000 is a correct answer
12 Correct 10 ms 2652 KB n = 3, 3000000000 is a correct answer
13 Correct 10 ms 4716 KB n = 3, 3000000000 is a correct answer
14 Correct 10 ms 2648 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 2652 KB n = 4, 4000000000 is a correct answer
16 Correct 10 ms 2680 KB n = 5, 4000000000 is a correct answer
17 Correct 10 ms 4700 KB n = 10, 1000000343 is a correct answer
18 Correct 10 ms 2652 KB n = 10, 3189 is a correct answer
19 Incorrect 10 ms 2652 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -