QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#50998#4823. No!IrisuWA 1ms3640kbC++143.0kb2022-09-30 08:55:342022-09-30 08:55: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-09-30 08:55:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3640kb
  • [2022-09-30 08:55:34]
  • 提交

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'