# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
630076 | chonka | Split the sequence (APIO14_sequence) | C++17 | 2067 ms | 36784 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 unsigned long long ull ;
#define fi first
#define se second
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MAXN = 1e5 + 7 ;
struct Line {
mutable ll k , m , p , id ;
bool operator < ( const Line& o ) const { return k < o.k ; }
bool operator < ( ll x ) const { return p < x ; }
};
struct LineContainer : multiset < Line , less < > > {
static const ll inf = LLONG_MAX ;
ll div ( ll a , ll b ) {
return a / b - ( ( a ^ b ) < 0 && a % b ) ;
}
bool isect ( iterator x , iterator y ) {
if ( y == end ( ) ) { return x->p = inf , 0 ; }
if ( x->k == y->k ) { x->p = x->m > y->m ? inf : -inf ; }
else { x->p = div ( y->m - x->m , x->k - y->k ) ; }
return x->p >= y->p ;
}
void add ( ll k , ll m , int id ) {
auto z = insert ( { k , m , 0 , id } ) , y = z ++ , x = y ;
while ( isect ( y , z ) ) { z = erase ( z ) ; }
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |