Submission #382772

#TimeUsernameProblemLanguageResultExecution timeMemory
382772ne4eHbKaPlanine (COCI21_planine)C++17
20 / 110
476 ms44348 KiB
#include <bits/stdc++.h> using namespace std; #ifndef _LOCAL //#pragma GCC optimize("O3,Ofast") #else #pragma GCC optimize("O0") #endif template<typename t> inline void umin(t &a, const t b) {a = min(a, b);} template<typename t> inline void umax(t &a, const t b) {a = max(a, b);} typedef pair<int, int> pii; typedef long long ll; typedef long double ld; typedef int8_t byte; ll time() {return chrono::system_clock().now().time_since_epoch().count();} mt19937 rnd(time()); #define ft first #define sd second #define len(f) int((f).size()) #define bnd(f) (f).begin(), (f).end() #define _ <<' '<< const int inf = 1e9 + 5; const ll inf64 = 4e18 + 5; const int md = 998244353; namespace MD { void add(int &a, const int b) {if((a += b) >= md) a -= md;} void sub(int &a, const int b) {if((a -= b) < 0) a += md;} int prod(const int a, const int b) {return ll(a) * b % md;} }; const int N = 1e6 + 5; int h, x[N], y[N], n, m; vector<pair<ld, ld>> c; ld f[N]; pii p[N]; bool mk[N]; ld point(int i, int j) { return f[m++] = x[j] + (x[j] - x[i]) * ll(h - y[j]) / ld(y[j] - y[i]); } void solve() { cin >> n >> h; for(int i = 0; i < n; ++i) cin >> x[i] >> y[i]; c.clear(); m = 0; for(int i = 2; i + 1 < n; i += 2) c.push_back({point(i, i - 1), point(i, i + 1)}); sort(f, f + m); m = unique(f, f + m) - f; n = 0; for(auto &i : c) { p[n++] = { lower_bound(f, f + m, i.ft) - f, lower_bound(f, f + m, i.sd) - f }; } sort(p, p + n); memset(mk, 0, n); for(int i = 1; i < n; ++i) if(p[i].ft == p[i - 1].ft && p[i].sd >= p[i - 1].sd) mk[i] = true; for(int i = n - 1, f = +inf; ~i; --i) { if(p[i].sd >= f) mk[i] = true; umin(f, p[i].sd); } int ans {}; for(int i = 0, f = -inf; i < n; ++i) { if(mk[i]) continue; if(f < p[i].ft) { f = p[i].sd; ++ans; } } cout << ans << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef _LOCAL // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); #else system("color a"); freopen("in.txt", "r", stdin); int t; cin >> t; while(t--) #endif solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...