| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 213393 | rqi | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
#define bk back()
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
int MOD = 998244353;
const int MX = 2e5+5;
const ld PI = acos((ld)-1);
template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
return b > a ? a = b, 1 : 0; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif
/**
* Description: Modular arithmetic operations. To make faster,
* change add and subtract so that they don't require \texttt{\%}.
* Source: KACTL
* Verification: https://open.kattis.com/problems/modulararithmetic
*/
struct mi {
int v; explicit operator int() const { return v; }
mi() { v = 0; }
mi(ll _v):v(_v%MOD) { v += (v<0)*MOD; }
};
mi& operator+=(mi& a, mi b) {
if ((a.v += b.v) >= MOD) a.v -= MOD;
return a; }
mi& operator-=(mi& a, mi b) {
if ((a.v -= b.v) < 0) a.v += MOD;
return a; }
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((ll)a.v*b.v); }
mi& operator*=(mi& a, mi b) { return a = a*b; }
mi pow(mi a, ll p) { assert(p >= 0); // asserts are important!
return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
mi inv(mi a) { assert(a.v != 0); return pow(a,MOD-2); }
mi operator/(mi a, mi b) { return a*inv(b); }
/// mi a = MOD+5; ps((int)inv(a));
typedef string str;
typedef vector<str> vs;
/**
* Description: LineContainer; add lines of the form $kx+m$,
* compute greatest $y$-coordinate for any $x$.
* Time: O(\log N)
* Source: KACTL
* https://github.com/kth-competitive-programming/kactl/commit/165807e28402c9be906f6e6a09452431787bb70d?diff=unified
* Verification:
* CSA Squared Ends not working :(
* https://codeforces.com/contest/1083/problem/E
* https://atcoder.jp/contests/arc066/tasks/arc066_d
*/
bool Q;
struct Line {
mutable ll k, m, p; // slope, y-intercept, last optimal x
ll eval (ll x) { return k*x+m; }
bool operator<(const Line& o) const { return Q?p<o.p:k<o.k; }
};
// for doubles, use inf = 1/.0, divi(a,b) = a/b
const ll inf = LLONG_MAX;
// floored div
ll divi(ll a, ll b) { return a/b-((a^b) < 0 && a%b); }
// last x such that first line is better
ll bet(const Line& x, const Line& y) {
if (x.k == y.k) return x.m >= y.m ? inf : -inf;
return divi(y.m-x.m,x.k-y.k); }
#define lb lower_bound
struct LC : multiset<Line> {
// updates x->p, determines if y is unneeded
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = inf; return 0; }
x->p = bet(*x,*y); return x->p >= y->p; }
void add(ll k, ll m) {
auto z = insert({k,m,0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());
Q = 1; auto l = *lb({0,0,x}); Q = 0;
return l.k*x+l.m;
}
};
LC stor[150005];
int n,ans[MX];
ll a[MX],b[MX],x[MX], y[MX];
int mn(ll x, ll y) {
int cur = 0;
R0F(i,18) {
int ind = cur+(1<<i); if (ind >= n) continue;
if (!sz(stor[ind]) || stor[ind].query(x) < y) cur = ind;
}
return cur+1;
}
void ins(int z, ll a, ll b) {
for (;z<=n;z+=(z&-z)) stor[z].add(a,b);
}
/*
int brute() {
}*/
/*int smart() {
}*/
int solve() {
cin >> n;
//F0R(i,n) cin >> a[i] >> b[i] >> x[i] >> y[i];
//assert(brute() == smart());
FOR(i,1,n+1) stor[i] = LC(); // OK
int mx = 0;
F0R(i,n) {
ll a,b,x,y; cin >> a >> b >> x >> y;
int z = mn(x,y); ans[i] = z-1; ckmax(mx,n-ans[i]);
if (ans[i]) ins(ans[i],a,b);
}
return mx;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
F0R(i,t) cout << solve() << "\n";
}