oj.uz

Submission #537512

# Submission time Handle Problem Language Result Execution time Memory
537512 2022-03-15T07:33:54 Z dantoh000 Planine (COCI21_planine) C++14
0 / 110
 4 ms 852 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
int n;
ll h;
ii p[1000005];
int Lid[1000005], Rid[1000005];
ii L[1000005], R[1000005];
int ord[1000005];
ll cross(ii x, ii y){
    return x.fi*y.se - x.se*y.fi;
}
bool cw(int a, int b, int c){
    ii x = ii(p[b].fi - p[a].fi, p[b].se - p[a].se);
    ii y = ii(p[c].fi - p[b].fi, p[c].se - p[b].se);
    return cross(x,y) < 0ll;
}
ii extrapolate(int a, int b){
    ll dy = p[b].se - p[a].se;
    ll dx = p[b].fi - p[a].fi;
    return ii(p[a].fi*dy + (h-p[a].se)*dx, dy);
}
bool cmp(ii a, ii b){
    //printf("comparing (%lld,%lld) and (%lld,%lld)\n",a.fi,a.se,b.fi,b.se);
    return a.fi*b.se < b.fi*a.se;
}
bool cmp3(ii a, ii b){
    //printf("comparing (%lld,%lld) and (%lld,%lld)\n",a.fi,a.se,b.fi,b.se);
    return a.fi*b.se <= b.fi*a.se;
}
bool cmp2(int a, int b){
    return cmp(R[a], R[b]);
}
int main(){
    scanf("%d%lld",&n,&h);
    p[0].fi = -1e13;
    p[0].se = h;
    for (int i = 1; i <= n; i++){
        scanf("%lld%lld",&p[i].fi,&p[i].se);
    }
    deque<int> dq;
    dq.push_back(0);
    dq.push_back(0);
    for (int i = 1; i <= n; i++){
        while (dq.size() > 2 && !cw(dq[dq.size()-2], dq[dq.size()-1], i)){
            dq.pop_back();
        }
        Lid[i] = dq.back();
        dq.push_back(i);
    }
    p[n+1].fi = 1e13;
    p[n+1].se = h;
    dq.clear();
    dq.push_back(n+1);
    dq.push_back(n+1);
    for (int i = n; i >= 1; i--){
        while (dq.size() > 2 && cw(dq[dq.size()-2], dq[dq.size()-1], i)){
            dq.pop_back();
        }
        Rid[i] = dq.back();
        dq.push_back(i);
    }
    for (int i = 1; i <= n; i++){
        L[i] = extrapolate(i,Lid[i]);
        R[i] = extrapolate(i,Rid[i]);
        //printf("%lld %lld, %lld %lld\n",L[i].fi,L[i].se, R[i].fi, R[i].se);
    }
    iota(ord+1,ord+n+1, 1);
    sort(ord+1, ord+n+1, cmp2);
    ii last = ii(-1e15,1);
    int ct=  0;
    for (int j = 1; j <= n; j++){
        int i = ord[j];
        if (i%2 == 0 || i == 1 || i == n) continue;
        //printf("range %d: ",i);
        //printf("%lld %lld vs %lld %lld\n",L[i].fi,L[i].se, last.fi, last.se);
        if (last == ii(-1e15,1) || !cmp3(L[i], last)){
            //printf("setting new R\n");
            last = R[i];
            ct++;
        }
    }
    printf("%d",ct);

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d%lld",&n,&h);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%lld%lld",&p[i].fi,&p[i].se);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Incorrect 4 ms 852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Incorrect 0 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Incorrect 4 ms 852 KB Output isn't correct
3 Halted 0 ms 0 KB -