Submission #537468

#	Time	Username	Problem	Language	Result	Execution time	Memory
537468		tqbfjotld	Planine (COCI21_planine)	C++14	110 / 110	322 ms	82616 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<pair<int,int> > hull[2];

void add(int x, int y, int no){
    while (hull[no].size()>1){
        auto t1 = hull[no].back();
        auto t2 = *----hull[no].end();
        bool b = (y-t1.second)*(x-t2.first)>=(x-t1.first)*(y-t2.second);
        if (no) b = !b;
        if (b){
            hull[no].pop_back();
        }
        else break;
    }
    hull[no].push_back({x,y});
}

pair<int,int> qu(int x, int y, int no){
    if (hull[no].size()==1){
        return hull[no][0];
    }
    int l = -1;
    int r = hull[no].size()-1;
    while (l+1<r){
        int mid = (l+r)/2;
        auto t1 = hull[no][mid+1];
        auto t2 = hull[no][mid];
        bool b = (y-t1.second)*(x-t2.first)>=(x-t1.first)*(y-t2.second);
        if (no) b = !b;
        if (b) r = mid;
        else l = mid;
    }
    return hull[no][r];
}

struct frac{
    int a, b;
    frac(){}
    frac(int _a, int _b){
        a = _a; b = _b;
    }
    bool operator<(frac other){
        return a*other.b<other.a*b;
    }
    bool operator<=(frac other){
        return a*other.b<=other.a*b;
    }
    bool operator==(frac other){
        return a*other.b==other.a*b;
    }
};

bool cmp(pair<frac,frac> a, pair<frac,frac> b){
    if (a.first==b.first) return a.second<b.second;
    else return a.first<b.first;
}

int X[1000005];
int Y[1000005];
frac L[1000005];
frac R[1000005];

 main(){
    int n,h;
    scanf("%lld%lld",&n,&h);
    if (n==3) {
        printf("0");
        return 0;
    }
    for (int x = 0; x<n; x++){
        scanf("%lld%lld",&X[x],&Y[x]);
    }
    for (int x = 0; x<n; x++){
        if (x==0) continue;
        if (x==n-1) continue;
        if (x&1){
            add(X[x],Y[x],0);
        }
        else{
            auto res = qu(X[x],Y[x],0);
            //printf("res: %lld %lld\n",res.first,res.second);
            //res = {X[x-1],Y[x-1]};
            L[x] = frac(X[x]*(res.second-Y[x])-(h-Y[x])*(X[x]-res.first),res.second-Y[x]);
        }
    }
    for (int x = n-2; x>0; x--){
        if (x&1){
            add(X[x],Y[x],1);
        }
        else{
            auto res = qu(X[x],Y[x],1);
            //res = {X[x+1],Y[x+1]};
            R[x] = frac(X[x]*(res.second-Y[x])+(h-Y[x])*(res.first-X[x]),res.second-Y[x]);
        }
    }
    vector<pair<frac,frac> > intervals;
    for (int x = 2; x<n-1; x+=2){
        intervals.push_back({R[x],L[x]});
    }
    sort(intervals.begin(),intervals.end(),cmp);
    frac cur = intervals[0].first;
    int ans = 1;
    for (auto x : intervals){
        //printf("interval %lld/%lld to %lld/%lld\n",x.first.a,x.first.b,x.second.a,x.second.b);
        if (x.second<=cur) continue;
        ans++;
        cur = x.first;
    }
    printf("%lld",ans);
}

/*

9 7
-999 0
-998 4
-1 2
0 4
1 0
3 4
4 2
998 4
999 0

*/

Compilation message (stderr)

Main.cpp:66:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 |  main(){
      |  ^~~~
Main.cpp: In function 'int main()':
Main.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%lld%lld",&n,&h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%lld%lld",&X[x],&Y[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60