QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56914#4814. Exciting TravelKING_UT#RE 0ms0kbC++202.0kb2022-10-21 21:34:342022-10-21 21:34:35

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-21 21:34:35]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2022-10-21 21:34:34]
  • 提交

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

output:


result: