# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
588338 | sofapuden | Aliens (IOI16_aliens) | C++14 | 1 ms | 232 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 "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = (1ll<<50);
const int mxN = 1e5+5;
struct line{
ll a, b;
int cn;
line(ll _a, ll _b, int _cn) : a(_a), b(_b), cn(_cn) {}
line(ll _a, ll _b) : line(_a, _b, 0) {}
ll eval(ll x){if(b == (1ll<<60))return (1ll<<60); return (x-a+1)*(x-a+1)+b;}
};
vector<int> vals;
struct LCT{
vector<line> st;
LCT(int n) : st(4*n,line(0,1ll<<60)) {}
void ins(line f, int l, int r, int p){
if(l > r)return;
int m = (l+r)>>1;
bool lf = st[p].eval(vals[l]) > f.eval(vals[l]);
bool mf = st[p].eval(vals[m]) > f.eval(vals[m]);
if(mf)swap(st[p],f);
if(lf == mf)ins(f,m+1,r,p<<1|1);
# | 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... |