QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#50998 | #4823. No! | Irisu | WA | 1ms | 3640kb | C++14 | 3.0kb | 2022-09-30 08:55:34 | 2022-09-30 08:55:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define per(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename T>void chkmax(T&x,T y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,T y){if(y<x)x=y;}
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define mem(x) memset((x),0,sizeof(x))
typedef double db;
typedef long long ll;
typedef vector<int>vi;
typedef pair<int,int>pii;
typedef unsigned u32;
typedef unsigned uint;
typedef unsigned long long u64;
namespace orzjk{
const int SZ=1e6;
char buf[SZ],*p1=buf,*p2=buf;
char nc(){
return p1==p2&&(p2=(p1=buf)+fread(buf,1,SZ,stdin),p1==p2)?EOF:*p1++;
}
char fub[SZ],*p3=fub,*p4=fub+SZ;
void pc(char c){
p3==p4&&(fwrite(fub,1,SZ,stdout),p3=fub);
*p3++=c;
}
void flush(){
fwrite(fub,1,p3-fub,stdout),p3=fub;
}
}
using orzjk::nc;
using orzjk::pc;
//#define nc getchar
//#define pc putchar
int read(){
int x=0,f=1;char c=nc();
while(c<48)c=='-'&&(f=-1),c=nc();
while(c>47)x=x*10+(c^48),c=nc();
return x*f;
}
void write(int x){
static char st[21];
if(!x)return pc(48),void();
char*p=st;
if(x<0)x=-x,pc('-');
for(;x;x/=10)*p++=x%10|48;
do{
pc(*--p);
}while(p!=st);
}
const int maxN=5e5+10;
const int maxV=4e6+10;
int n,q;
struct frac{
int u,d;
frac(){}
frac(int x,int y){
u=x,d=y;
// int g=__gcd(x,y);
// u=x/g,d=y/g;
}
bool operator<(const frac&o)const{
return 1ll*u*o.d<1ll*o.u*d;
}
void print(){
printf("!(%d %d)\n",u,d);
}
void reduce(){
ll g=__gcd(u,d);
u/=g,d/=g;
}
}ans[maxN];
struct point{
int x,y;
};
frac cross(point P,point Q){
return frac(P.y-Q.y,P.x-Q.x);
}
struct Querys{
int v,id;
}Q[maxN];
int s[maxV];
void solve(){
int vsz=0;
n=read(),q=read();
rep(i,1,n){
int h=read(),s=read();
chkmax(::s[h],s),chkmax(vsz,h);
}
rep(i,1,q){
Q[i]={read(),i};
}
sort(Q+1,Q+q+1,[](Querys P,Querys Q){
return P.v>Q.v;
});
frac cur(1,0);
vector<point>st;
for(int i=vsz,j=1;i;i--){
for(;j<=q&&Q[j].v>=i;j++){
ans[Q[j].id]=cur;
}
if(s[i]){
point ths={i,s[i]};
while((st.size()>1u&&cross(st.back(),ths)<cross(st[st.size()-2],st.back()))||(!st.empty()&&st.back().y<=s[i]))st.pop_back();
st.pb(ths);
}
while(st.size()>1u&&cross({i-1,0},st.back())<cross({i-1,0},st[st.size()-2]))st.pop_back();
frac res=cross({i-1,0},st.back());
// for(point p:st)chkmax(res,cross({i-1,0},p));
// frac res(0,1);
// rep(p,i,vsz)chkmax(res,frac(s[p],p-i+1));
// printf("(%d %d)\n",res.u,res.d);
chkmin(cur,res);
}
rep(i,1,q)ans[i].reduce(),write(ans[i].u),pc('/'),write(ans[i].d),pc(10);
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// int T;cin>>T;while(T--)solve();
solve();
orzjk::flush();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3640kb
input:
4 5 3 5 4 3 2 5 6 3 5 2 3 7 2
output:
1/0 1/0 1/0 1/0 1/0
result:
wrong answer 1st lines differ - expected: '3/1', found: '1/0'