# | 제출 시각UTC-0 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
81548 | kimjg1119 | 수열 (APIO14_sequence) | C11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
pli query(ll x){