# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
81520 | kimjg1119 | Split the sequence (APIO14_sequence) | C++17 | 25 ms | 11856 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>
#define MAXN 100005
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef struct CHT{
ll la[MAXN], lb[MAXN]; int lz[MAXN];
int stkn=0,pt=1;
void insert(ll a, ll b, int z){
while(stkn>pt){
if(a==la[stkn] && b>=lb[stkn]) stkn--;
else if((lb[stkn]-b)*(la[stkn]-la[stkn-1])<(a-la[stkn])*(lb[stkn-1]-lb[stkn])) stkn--;
else break;
}
// (lb[stkn]-b)/(a-la[stkn]) <(lb[stkn-1]-lb[stkn])/(la[stkn]-la[stkn-1]) 일 때 stkn--; 인데
// 기울기가 일정하게 되면 a-la[stkn] 또는 la[stkn]-la[stkn-1]이 0이 될 수 있음.
// la[stkn]==la[stkn-1] 이거나 a==la[stkn]인 상황이 오면 교점이 존재하지 않음.
// la[stkn]==la[stkn-1] 인 상황이 없다고 가정하자. 그러면 a==la[stkn]인 상황만 처리해주면 됨.
// 두 직선의 기울기가 같으면 y절편이 큰 직선을 남기는 게 이득이라는 것이 자명함.
if(a==la[stkn] && b>=lb[stkn] && z!=0){
lz[stkn]=z;
return;
}
la[++stkn]=a;
lb[stkn]=b;
lz[stkn]=z;
Compilation message (stderr)
# | 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... |