Submission #988653

#	Time	Username	Problem	Language	Result	Execution time	Memory
988653		Aviansh	Building Bridges (CEOI17_building)	C++17	0 / 100	16 ms	600 KiB

building

#include <bits/stdc++.h>

using namespace std;

struct line{
    double m,c;
    double eval(double x){
        return (m*x)+c;
    }
    double intersect(line l){
        return (l.c-c)/(m-l.m);
    }
};

template<class T> class liChaoTree{
    private:
        int n;
        line *st;
        line def = {0,INT_MAX};
    public:
        liChaoTree(int siz){
            int x = (int) pow(2,ceil(log2(siz)));
            n=siz-1;
            st=new line[2*x];
            realST(0,n,0);
        }
        void realST(int l, int r, int ind){
            st[ind]=def;
            if(l!=r){
                int mid = (l+r)/2;
                realST(l,mid,ind*2+1);
                realST(mid+1,r,ind*2+2);
            }
        }
        double realQuer(double x, int l, int r, int ind){
            int mid = (l+r)/2;
            if(r-l==1){
                return st[ind].eval(x);
            }
            else if(x<mid){
                return min(st[ind].eval(x),realQuer(x,l,mid,ind*2+1));
            }
            else{
                return min(st[ind].eval(x),realQuer(x,mid,r,ind*2+2));
            }
        }
        double quer(double x){
            return realQuer(x,0,n,0);
        }
        void realUpdate(int s, int e, line nw, int ind){
            int mid = (s+e)/2;
            bool lef = st[ind].eval(s) > nw.eval(s);
            bool mi = st[ind].eval(mid) > nw.eval(mid);
            if(mi){
                swap(st[ind],nw);
            }
            if(e-s==1){
                return;
            }
            else if(lef!=mi){
                realUpdate(s,mid,nw,ind*2+1);
            }
            else{
                realUpdate(mid,e,nw,ind*2+2);
            }
        }
        void addLine(line l){
            realUpdate(0,n,l,0);
        }
};

signed main(){
    liChaoTree<int> lct(20);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    for(int i = 0;i<n;i++){
        int m,c;
        cin >> m >> c;
        line l;
        l.m=m;
        l.c=c;
        lct.addLine(l);
    }
    while(q--){
        int t;
        cin >> t;
        if(t==0){
            line l;
            int m,c;
            cin >> m >> c;
            l.m=m;l.c=c;
            lct.addLine(l);
        }
        else{
            int x;
            cin >> x;
            cout << lct.quer(x) << endl;
        }
    }
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40