Submission #888184

#TimeUsernameProblemLanguageResultExecution timeMemory
888184heavylightdecompTri (CEOI09_tri)C++14
40 / 100
129 ms65536 KiB
#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 const int maxn = 2e5+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]; 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); seg_upd(1, 1, roll-1, linp[i], i); } // free(points); // free(linp); for(int g = 1; g <= M; g++) { 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:196:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<rational, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |     while(ptr < mps.size()) {
      |           ~~~~^~~~~~~~~~~~
tri.cpp:199:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<rational, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |         while(ptr < mps.size() and mps[ptr].x == cur) {
      |               ~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...