求调

P3081 [USACO13MAR] Hill Walk G

Arrtan_73 @ 2024-07-16 11:38:35

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct line{
    int xa, xb, ya, yb;
    double b, k;
    double operator [](int x){return k * x + b;}
    bool operator <(line x){return x.xa > xa;}
}lin[N];
int temp[N << 1], top;
int siz, n, ans;
int tree[N << 3];
bool cmp(const line a, const int b){return a.xa <= b;}
void addline(int id){
    lin[id].k = (double)(lin[id].ya - lin[id].yb) / (lin[id].xa - lin[id].xb);
    lin[id].b = (double)lin[id].ya - lin[id].k * lin[id].xa;
    return;
}
void add(int p, int L, int R, int l, int r, int id){
    int mid = (L + R) >> 1;
    if(l <= L && R <= r){
        if(!tree[p] || (lin[tree[p]][L] < lin[id][L] && lin[tree[p]][R] < lin[id][R])){
            tree[p] = id;
            return;
        }
        if(L == R || (lin[tree[p]][L] > lin[id][L] && lin[tree[p]][R] > lin[id][R]))return;
        if(lin[tree[p]][mid] < lin[id][mid])swap(tree[p], id);
        if(lin[tree[p]][L] <= lin[id][L])add(p << 1, L, mid, l, r, id);
        else if(lin[tree[p]][R] <= lin[id][R])add(p << 1, mid + 1, R, l, r, id); 
    }
    else{
        if(l <= mid)add(p << 1, L, mid, l, r, id);
        if(mid < r)add(p << 1 | 1, mid + 1, R, l, r, id);
    }
    return;
}
void getans(int p, int L, int R, int k){
    if(tree[p] && lin[tree[p]][k] > lin[ans][k])ans = tree[p];
    if(L == R)return;
    int mid = (L + R) / 2;
    if(k <= mid)getans(p * 2, L, mid, k);
    else getans(p * 2 + 1, mid + 1, R, k);
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    lin[0].k = lin[0].b = -1;
    for(int i = 1; i <= n; i++){
        cin >> lin[i].xa >> lin[i].ya >> lin[i].xb >> lin[i].yb;
        temp[++top] = lin[i].xa;
        temp[++top] = lin[i].xb;
    }
    sort(temp + 1, temp + top + 1);
    sort(lin + 1, lin + n + 1);
    top = unique(temp + 1, temp + top + 1) - (temp + 1);
    for(int i = 1; i <= n; i++){
        lin[i].xa = lower_bound(temp + 1, temp + top + 1, lin[i].xa) - temp;
        lin[i].xb = lower_bound(temp + 1, temp + top + 1, lin[i].xb) - temp;
        addline(i);
        //cout << lin[i].xa << " " << lin[i].ya << " " << lin[i].xb << " " << lin[i].yb << " " << lin[i].b << " " << lin[i].k << endl;
    }
    int cnt = 1, pos = 1, ed = 0;
    while(1){
        int r = lower_bound(lin + 1, lin + n + 1, lin[pos].xb, cmp) - (lin + 1);
        //cout << r << endl;
        for(int i = ed + 1; i <= r; i++){
            //cout << lin[pos][lin[i].xa] << endl;
            if(lin[i].ya <= lin[pos][lin[i].xa])add(1, 0, N << 1, lin[i].xa, lin[i].xb, i);
        }
        ed = r;
        ans = 0;
        getans(1, 0, N << 1, lin[pos].xb + 1);
        //cout << ans << endl;
        if(ans)pos = ans, cnt++;
        else break;
    }
    cout << cnt;
    return 0;
}
/*
2
0 0 1 3
4 5 7 6
*/

by Arrtan_73 @ 2024-07-16 11:38:52

只有 65pts


by Arrtan_73 @ 2024-07-16 11:58:02

update

else if(lin[tree[p]][R] <= lin[id][R])add(p << 1, mid + 1, R, l, r, id); 

改为

else if(lin[tree[p]][R] <= lin[id][R])add(p << 1 | 1, mid + 1, R, l, r, id); 

by Arrtan_73 @ 2024-07-16 11:58:21

但还是错的


|