QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56914 | #4814. Exciting Travel | KING_UT# | RE | 0ms | 0kb | C++20 | 2.0kb | 2022-10-21 21:34:34 | 2022-10-21 21:34:35 |
Judging History
answer
#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define bg begin()
#define ed end()
#define pb push_back
#define eb emplace_back
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t>using vc=vector<t>;
template<class t>using vvc=vc<vc<t>>;
template<class t,class u>bool chmin(t&a,u b){
if(a>b){a=b;return true;}
else return false;
}
template<class t,class u>bool chmax(t&a,u b){
if(a<b){a=b;return true;}
else return false;
}
const ll inf=LLONG_MAX/3;
#define a first
#define b second
using pi=pair<int,int>;
struct Line{
mutable ll a,b,p;
bool operator<(const Line&o)const{return a>o.a;}
bool operator<(ll x)const{return p<x;}
};
struct LineContainer:multiset<Line,less<>>{
ll div(ll a,ll b){return a/b-((a^b)<0&&a%b);}
bool isect(iterator x, iterator y){
if(y==end()){x->p=inf;return false;}
if(x->a==y->a) x->p=x->b<y->b?inf:-inf;
else x->p=div(x->a*y->b-y->a*x->b,x->a-y->b);
return x->p>=y->p;
}
void add(ll a,ll b){
auto z=insert({a,b,0}),y=z++,x=y;
while(isect(y,z))z=erase(z);
if(x!=bg&&isect(--x,y))isect(x,y=erase(y));
while((y=x)!=bg&&(--x)->p>=y->p)isect(x,erase(y));
}
pi query(ll x){
if(empty())return pi(0,1);
auto l=lower_bound(x);
return pi(l->b-x,l->a);
}
};
bool fless(pi a,pi b){
return a.a*b.b<a.b*b.a;
}
void slv(){
int n,q;cin>>n>>q;
vc<pi> hs(n+q);
rep(i,n){
int h,s;cin>>h>>s;
hs[i]=pi(h,s);
}
rep(i,q){
int h;cin>>h;
hs[n+i]=pi(h,i-q);
}
sort(all(hs),greater<pi>());
vc<pi> ans(q);
pi pre(0,1);
LineContainer lc;
for(auto [h,s]:hs){
pi g=lc.query(h);
if(fless(g,pre))g=pre;
pre=g;
if(s<0){
ans[s+q]=g;
}else{
lc.add(h,s);
}
}
for(auto [a,b]:ans){
int g=gcd(a,b);
cout<<b/g<<"/"<<a/g<<"\n";
}
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
slv();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
5 3 1 2 1 3 2 4 2 5 3 1 4 5 4 1 2 4 3 4 2 4 5 1