Submission #893652

#	Time	Username	Problem	Language	Result	Execution time	Memory
893652		heavylightdecomp	Tri (CEOI09_tri)	C++14	80 / 100	382 ms	65536 KiB

tri

#include<bits/stdc++.h>
using namespace std;
#define cerr while(0) cerr
#define ld long double
#define x first
#define y second
#define vt vector
#define pb push_back
#define wassert(x) do { if(not (x)) { cout << -329032 << '\n'; exit(0); } } while(0)
const int maxn = 1e5+5;
int K,M;
struct line {
    ld m;
    ld c;
    line() {}
    line(ld a, ld b) {
        m = a;
        c = b;
    }
};
ld interx(line a, line b) {
    ld res = (ld)(b.c - a.c) / (ld)(a.m - b.m);
    return res;
}
line alns[maxn];
struct cht {
    bool PREPPED = 0;
    vt<int> emb;
    vt<pair<ld, int>> sta;
    void push(int lne) {
        if(PREPPED) {
            cerr << "Tried inserting on query-only mode!\n";
            // assert(1 == 2);
        }
        emb.push_back(lne);
    }
    bool bye(pair<ld, int> g, line h) {
        ld cut = g.first;
        if(interx(alns[g.second], h) <= cut) {
            return true;
        }
        return false;
    }
    void solve() {
        //BUG: without the capture clause it is undefined behaviour?
        sort(begin(emb), end(emb), [&](int a, int b) {if(alns[a].m == alns[b].m) return alns[a].c > alns[b].c; else return alns[a].m > alns[b].m; }); //BUG: Did not account for equal gradients
        for(int c: emb) {
            line curr = alns[c];
            while(sta.size() and (alns[sta.back().second].m == curr.m or bye(sta.back(), curr))) {
                sta.pop_back();
            }
            ld ccut = -1e18;
            if(sta.size()) {
                ccut = interx(curr, alns[sta.back().second]);
            }
            if(ccut <= 1e18) sta.push_back({ccut, c});
        }
        // cerr << "Yep done\n";
        emb.clear();
    }
    bool query(ld x, ld maxy) {
        if(not PREPPED) { //BUG: Solve needs to always be before stack condition
            cerr << "Query-only mode activated\n";
            solve();
            PREPPED = true;
        }
        cerr << "I can reach this\n";
        if(sta.empty()) { //BUG: should've checked empty case
            return false;
        }
        
        auto lb = upper_bound(begin(sta), end(sta), x, 
            [](ld q, pair<ld, int> a) { 
                return q < a.first;
            }
        ); //BUG: Upper bound was so much more weird compared to lower bound
        //Otherwise code was good, trust your code.
        // assert(lb != begin(sta));
        lb = prev(lb);
        line now = alns[lb->second];
        ld lhs = (now.m * (ld)x + now.c);
        return lhs <= (ld)maxy;
    }
};
 
struct rational {
    int p, q;
    rational() {}
    rational(int a, int b) {
        p = a, q = b;
    }
    friend bool operator==(rational a, rational x) {
        if(x.q == a.q and a.q == 0) {
            return true; 
        } else if((x.q == 0 and a.q != 0) or (x.q != 0 and a.q == 0)) {
            return false;
        }
        long long lhs = a.p * x.q;
        long long rhs = a.q * x.p;
        return lhs == rhs;
    }
    friend bool operator<(rational a, rational x) {
        // assert(a.p >= 0 and a.q >= 0);
        // assert(x.p >= 0 and x.q >= 0);
        if(a.q == 0) return false;
        if(x.q == 0) return true;
        long long lhs = 1ll * a.p * x.q;
        long long rhs = 1ll * a.q * x.p;
        return lhs < rhs;
    } 
};
cht st[4*maxn];
bool seg_query(int x, int tl, int tr, int l, int r, ld m, ld b) {
    if(tl == l and tr == r) { //BUG: l == r instead of tl == l and tr == r
        return st[x].query(m, b);
    }
    // assert(tl <= l and r <= tr);
    int tm = (tl+tr)/2;
    bool res = 0; 
    if(l <= tm) {
        res = res or seg_query(x*2, tl, tm, l, min(tm,r), m, b); //BUG: should be l, min(tm,r)
    }
    if(tm < r) {
        res = res or seg_query(x*2+1, tm+1, tr, max(tm+1,l), r, m, b); //BUG: should be max(tm+1,l), r
    }
    return res;
}
void seg_upd(int x, int tl, int tr, int pseu, int lne) {
    if(tl == tr) {
        st[x].push(lne);
        return;
    }
    int tm = (tl+tr)/2;
    st[x].push(lne);
    if(pseu <= tm) {
        seg_upd(x*2, tl, tm, pseu, lne);
    } else {
        seg_upd(x*2+1, tm+1, tr, pseu, lne);
    }
}
// struct seg {
//     int tl, tr;
//     seg *lc, *rc;
//     cht db;
//     bool has_child = 0;
//     seg() {}
//     seg(int a, int b) {
//         tl = a, tr = b;
//     }
//     void split() {
//         if(has_child or tl == tr) return;
//         has_child = true;
//         int tm = (tl+tr)/2;
//         lc = new seg(tl, tm);
//         rc = new seg(tm+1, tr);
//     }
//     bool query(int l, int r, ld m, ld b) {
        
//     }
//     void upd(int pseu, line u) {
 
//     }
// };
pair<ld, ld> qs[maxn];
pair<int, int> points[maxn];
bool ans[maxn];
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> K >> M;
    // vector<pair<rational, int>> mps; //object id
    vt<rational> cdnat;
    for(int i = 1; i <= K; i++) {
        int xp, yp;
        cin >> xp >> yp;
        // cerr << (rational(1,1) == rational(2,2)) << '\n';
        // cht.push(line(-xp, yp));
        cdnat.pb(rational(yp, xp));
        points[i] = {xp, yp};
    }
    int ptr = 0;
    int roll = 1; 
    sort(begin(cdnat), end(cdnat)); //upd roll = cdnat size
    unique(begin(cdnat), end(cdnat));
    map<rational, int> compy;
    for(int g = 0; g < cdnat.size(); g++) {
        rational i = cdnat[g];
        compy[i] = g+1;
    }
    roll = cdnat.size() + 1;
    // cht.solve();
    for(int i = 1; i <= K; i++) {
        int xp = points[i].x, yp = points[i].y;
        //REMEMBER: (-xp, yp) for line
        alns[i] = line(-xp, yp);
        seg_upd(1, 1, roll-1, compy[rational(yp, xp)], i);
    }
    for(int g = 1; g <= M; g++) { //Lines as queries: need qran[g] = something
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        rational lo (y1, x1), hi (y2, x2);
        if(hi < lo) swap(lo, hi);
        ld m = ((ld)(y2 - y1)) / ((ld)(x2 - x1));
        ld b = -m * (ld)x1 + (ld)y1;
        auto lef = compy.lower_bound(lo);
        auto erig = compy.upper_bound(hi);
        if(lef == compy.end() or erig == compy.begin()) {
            cout << "N\n";
        } else {
            int ql = lef->second, qr = prev(erig)->second;
            bool res = seg_query(1,1,roll-1,ql,qr,m,b);
            if(res) {
                cout << "Y\n";
            } else {
                cout << "N\n";
            }
        }
        // mps.push_back({lo, g+K});
        // mps.push_back({hi, g+K});
        // cerr << m << ' ' << b << '\n';
        // bool res = cht.query(m, b);
        // qs[g] = {m, b};
    }
    
    //reduce memory: store
    // sort(begin(mps), end(mps), [](pair<rational, int> a, pair<rational,int> b) { return a.x < b.x; });
    // while(ptr < mps.size()) {
    //     vector<int> these;
    //     rational cur = mps[ptr].x;
    //     while(ptr < mps.size() and mps[ptr].x == cur) {
    //         these.push_back(mps[ptr].y);
    //         ptr++;
    //     }
    //     for(int it : these) {
    //         if(it <= K) {
    //             linp[it] = roll;
    //         } else {
    //             //AVOIDED BUG: it -= K;
    //             it -= K;
    //             if(qran[it].x == 0) {
    //                 qran[it].x = roll;
    //             } else {
    //                 qran[it].y = roll;
    //             }
    //         }
    //     }
    //     roll++;
    // }
    // seg* root = new seg(1, roll-1);
    
    // free(points);
    // free(linp);
    // for(int g = 1; g <= M; g++) {
    //     int lef = compy[]
    //     ans[g] = seg_query(1, 1, roll-1, qran[g].x, qran[g].y, qs[g].x, qs[g].y);
    // }
    // for(int i = 1; i <= M; i++) {
    //     if(ans[i]) {
    //         cout << "Y\n";
    //     } else {
    //         cout << "N\n";
    //     }
    // }
 
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:186:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rational>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for(int g = 0; g < cdnat.size(); g++) {
      |                    ~~^~~~~~~~~~~~~~
tri.cpp:181:9: warning: unused variable 'ptr' [-Wunused-variable]
  181 |     int ptr = 0;
      |         ^~~

• Subtask 1: 80 / 100