Submission #888176

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888176	2023-12-16T09:37:18 Z	heavylightdecomp	Tri (CEOI09_tri)	C++14	Compilation error	0 ms	0 KB

tri

#include<bits/stdc++.h>
using namespace std;
#define cerr while(0) cerr
#define ld long double
#define int long long
#define EPS (ld)(2e-9)
#define x first
#define y second
#define vt vector
const int maxn = 2e5+5;
int K,M;
line alns[maxn];
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;
}
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() {
        sort(begin(emb), end(emb), [](line a, line b) {if(a.m == b.m) return a.c > b.c; else return a.m > b.m; }); //BUG: Did not account for equal gradients
        for(int _c: emb) {
            line curr = alns[emb[_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";
    }
    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, line> 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;
        }
        return a.p * x.q == a.q * x.p;
    }
    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;
        return a.p * x.q < a.q * x.p;
    } 
};
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) {
        if(tl == l and tr == r) { //BUG: l == r instead of tl == l and tr == r
            return db.query(m, b);
        }
        assert(tl <= l and r <= tr);
        int tm = (tl+tr)/2;
        split();
        bool res = 0; 
        if(l <= tm) {
            res = res or lc->query(l, min(tm,r), m, b); //BUG: should be l, min(tm,r)
        }
        if(tm < r) {
            res = res or rc->query(max(tm+1,l), r, m, b); //BUG: should be max(tm+1,l), r
        }
        return res;
    }
    void upd(int pseu, int lne) {
        if(tl == tr) {
            db.push(lne);
            return;
        }
        int tm = (tl+tr)/2;
        split();
        db.push(lne);
        if(pseu <= tm) {
            lc->upd(pseu, lne);
        } else {
            rc->upd(pseu, lne);
        }
    }
};
pair<ld, ld> qs[maxn];
pair<int, int> points[maxn];
bool ans[maxn];
int linp[maxn]; //pseudo gradient of a point
pair<int, int> qran[maxn]; //pseudo gradients of query ranges
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> K >> M;
    vector<pair<rational, int>> mps; //object id
    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));
        mps.push_back({rational(yp, xp), i});
        points[i] = {xp, yp};
    }
    // cht.solve();
    for(int g = 1; g <= M; g++) {
        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;
        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};
    }
    int ptr = 0;
    int roll = 1;
    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);
    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);
        root->upd(linp[i], i);
    }
    for(int g = 1; g <= M; g++) {
        ans[g] = root->query(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

tri.cpp:12:1: error: 'line' does not name a type
   12 | line alns[maxn];
      | ^~~~
tri.cpp: In member function 'bool cht::bye(std::pair<long double, long long int>, line)':
tri.cpp:39:19: error: 'alns' was not declared in this scope
   39 |         if(interx(alns[g.second], h) <= cut) {
      |                   ^~~~
tri.cpp: In member function 'void cht::solve()':
tri.cpp:47:25: error: 'alns' was not declared in this scope
   47 |             line curr = alns[emb[_c]];
      |                         ^~~~
tri.cpp: In member function 'bool cht::query(long double, long double)':
tri.cpp:77:20: error: 'alns' was not declared in this scope
   77 |         line now = alns[lb->second];
      |                    ^~~~
tri.cpp: In function 'int main()':
tri.cpp:185:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<rational, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |     while(ptr < mps.size()) {
      |           ~~~~^~~~~~~~~~~~
tri.cpp:188:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<rational, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |         while(ptr < mps.size() and mps[ptr].x == cur) {
      |               ~~~~^~~~~~~~~~~~
tri.cpp:211:9: error: 'alns' was not declared in this scope; did you mean 'ans'?
  211 |         alns[i] = line(-xp, yp);
      |         ^~~~
      |         ans
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from tri.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = const long double; _Iterator = __gnu_cxx::__normal_iterator<std::pair<long double, long long int>*, std::vector<std::pair<long double, long long int> > >; _Compare = cht::query(long double, long double)::<lambda(long double, std::pair<long double, line>)>]':
/usr/include/c++/10/bits/stl_algo.h:2061:14:   required from '_ForwardIterator std::__upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<long double, long long int>*, std::vector<std::pair<long double, long long int> > >; _Tp = long double; _Compare = __gnu_cxx::__ops::_Val_comp_iter<cht::query(long double, long double)::<lambda(long double, std::pair<long double, line>)> >]'
/usr/include/c++/10/bits/stl_algo.h:2128:32:   required from '_FIter std::upper_bound(_FIter, _FIter, const _Tp&, _Compare) [with _FIter = __gnu_cxx::__normal_iterator<std::pair<long double, long long int>*, std::vector<std::pair<long double, long long int> > >; _Tp = long double; _Compare = cht::query(long double, long double)::<lambda(long double, std::pair<long double, line>)>]'
tri.cpp:73:9:   required from here
/usr/include/c++/10/bits/predefined_ops.h:238:23: error: no match for call to '(cht::query(long double, long double)::<lambda(long double, std::pair<long double, line>)>) (const long double&, std::pair<long double, long long int>&)'
  238 |  { return bool(_M_comp(__val, *__it)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h:238:23: note: candidate: 'bool (*)(long double, std::pair<long double, line>)' (conversion)
/usr/include/c++/10/bits/predefined_ops.h:238:23: note:   candidate expects 3 arguments, 3 provided
tri.cpp:70:13: note: candidate: 'cht::query(long double, long double)::<lambda(long double, std::pair<long double, line>)>'
   70 |             [](ld q, pair<ld, line> a) {
      |             ^
tri.cpp:70:13: note:   no known conversion for argument 2 from 'pair<[...],long long int>' to 'pair<[...],line>'
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from tri.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Iterator2 = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = cht::solve()::<lambda(line, line)>]':
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = cht::solve()::<lambda(line, line)>]'
tri.cpp:45:113:   required from here
/usr/include/c++/10/bits/predefined_ops.h:156:30: error: no match for call to '(cht::solve()::<lambda(line, line)>) (long long int&, long long int&)'
  156 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h:156:30: note: candidate: 'bool (*)(line, line)' (conversion)
/usr/include/c++/10/bits/predefined_ops.h:156:30: note:   candidate expects 3 arguments, 3 provided
tri.cpp:45:36: note: candidate: 'cht::solve()::<lambda(line, line)>'
   45 |         sort(begin(emb), end(emb), [](line a, line b) {if(a.m == b.m) return a.c > b.c; else return a.m > b.m; }); //BUG: Did not account for equal gradients
      |                                    ^
tri.cpp:45:36: note:   no known conversion for argument 1 from 'long long int' to 'line'
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from tri.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = long long int; _Iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = cht::solve()::<lambda(line, line)>]':
/usr/include/c++/10/bits/stl_algo.h:1826:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:1854:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:1886:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:1977:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = cht::solve()::<lambda(line, line)>]'
tri.cpp:45:113:   required from here
/usr/include/c++/10/bits/predefined_ops.h:238:23: error: no match for call to '(cht::solve()::<lambda(line, line)>) (long long int&, long long int&)'
  238 |  { return bool(_M_comp(__val, *__it)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h:238:23: note: candidate: 'bool (*)(line, line)' (conversion)
/usr/include/c++/10/bits/predefined_ops.h:238:23: note:   candidate expects 3 arguments, 3 provided
tri.cpp:45:36: note: candidate: 'cht::solve()::<lambda(line, line)>'
   45 |         sort(begin(emb), end(emb), [](line a, line b) {if(a.m == b.m) return a.c > b.c; else return a.m > b.m; }); //BUG: Did not account for equal gradients
      |                                    ^
tri.cpp:45:36: note:   no known conversion for argument 1 from 'long long int' to 'line'
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from tri.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Value = long long int; _Compare = cht::solve()::<lambda(line, line)>]':
/usr/include/c++/10/bits/stl_heap.h:139:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Distance = long int; _Tp = long long int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_heap.h:246:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Distance = long int; _Tp = long long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_heap.h:355:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:1666:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:1937:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:1953:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<cht::solve()::<lambda(line, line)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = cht::solve()::<lambda(line, line)>]'
tri.cpp:45:113:   required from here
/usr/include/c++/10/bits/predefined_ops.h:194:23: error: no match for call to '(cht::solve()::<lambda(line, line)>) (long long int&, long long int&)'
  194 |  { return bool(_M_comp(*__it, __val)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h:194:23: note: candidate: 'bool (*)(line, line)' (conversion)
/usr/include/c++/10/bits/predefined_ops.h:194:23: note:   candidate expects 3 arguments, 3 provided
tri.cpp:45:36: note: candidate: 'cht::solve()::<lambda(line, line)>'
   45 |         sort(begin(emb), end(emb), [](line a, line b) {if(a.m == b.m) return a.c > b.c; else return a.m > b.m; }); //BUG: Did not account for equal gradients
      |                                    ^
tri.cpp:45:36: note:   no known conversion for argument 1 from 'long long int' to 'line'