#include <bits/stdc++.h>
using namespace std;
struct line{
double m,c;
double eval(double x){
return (m*x)+c;
}
double intersect(line l){
return (l.c-c)/(m-l.m);
}
};
template<class T> class liChaoTree{
private:
int n;
line *st;
line def = {0,INT_MAX};
public:
liChaoTree(int siz){
int x = (int) pow(2,ceil(log2(siz)));
n=siz-1;
st=new line[2*x];
realST(0,n,0);
}
void realST(int l, int r, int ind){
st[ind]=def;
if(l!=r){
int mid = (l+r)/2;
realST(l,mid,ind*2+1);
realST(mid+1,r,ind*2+2);
}
}
double realQuer(double x, int l, int r, int ind){
int mid = (l+r)/2;
if(r-l==1){
return st[ind].eval(x);
}
else if(x<mid){
return min(st[ind].eval(x),realQuer(x,l,mid,ind*2+1));
}
else{
return min(st[ind].eval(x),realQuer(x,mid,r,ind*2+2));
}
}
double quer(double x){
return realQuer(x,0,n,0);
}
void realUpdate(int s, int e, line nw, int ind){
int mid = (s+e)/2;
bool lef = st[ind].eval(s) > nw.eval(s);
bool mi = st[ind].eval(mid) > nw.eval(mid);
if(mi){
swap(st[ind],nw);
}
if(e-s==1){
return;
}
else if(lef!=mi){
realUpdate(s,mid,nw,ind*2+1);
}
else{
realUpdate(mid,e,nw,ind*2+2);
}
}
void addLine(line l){
realUpdate(0,n,l,0);
}
};
signed main(){
liChaoTree<int> lct(20);
ios::sync_with_stdio(0);
cin.tie(0);
int n,q;
cin >> n >> q;
for(int i = 0;i<n;i++){
int m,c;
cin >> m >> c;
line l;
l.m=m;
l.c=c;
lct.addLine(l);
}
while(q--){
int t;
cin >> t;
if(t==0){
line l;
int m,c;
cin >> m >> c;
l.m=m;l.c=c;
lct.addLine(l);
}
else{
int x;
cin >> x;
cout << lct.quer(x) << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
