QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#50794#4823. No!IrisuWA 1108ms10064kbC++142.8kb2022-09-29 12:36:572022-09-29 12:37:00

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-29 12:37:00]
  • 评测
  • 测评结果:WA
  • 用时:1108ms
  • 内存:10064kb
  • [2022-09-29 12:36:57]
  • 提交

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){
    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;
  }
}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.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));
    chkmin(cur,res);
  }
  rep(i,1,q)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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 9724kb

input:

4 5
3 5
4 3
2 5
6 3
5
2
3
7
2

output:

3/1
3/2
3/2
1/0
3/2

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 3ms
memory: 9656kb

input:

5 6
10 6
3 7
6 15
7 6
8 15
5
3
9
7
7
9

output:

3/1
3/1
6/1
3/1
3/1
6/1

result:

ok 6 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 9772kb

input:

5 6
7 2020
1 8
10 1
8 1975
6 10
2
9
3
4
9
5

output:

1/2
1/1
1/2
1/2
1/1
1/2

result:

ok 6 lines

Test #4:

score: 0
Accepted
time: 3ms
memory: 9636kb

input:

1 1
8 9
8

output:

1/0

result:

ok single line: '1/0'

Test #5:

score: 0
Accepted
time: 2ms
memory: 9760kb

input:

1 1
3 1
6

output:

1/0

result:

ok single line: '1/0'

Test #6:

score: 0
Accepted
time: 2ms
memory: 9844kb

input:

7 9
44 51
91 191
1 6
67 3
94 191
87 58
59 10
54
80
37
63
27
9
28
85
44

output:

191/37
191/11
191/47
191/28
3/1
191/82
51/16
191/6
191/47

result:

ok 9 lines

Test #7:

score: 0
Accepted
time: 2ms
memory: 9780kb

input:

7 9
56 11172
5 9
79 2674
31 3263
38 4607
36 5
82 1814
41
24
52
22
30
92
74
48
67

output:

2674/23
2674/23
2674/23
2674/23
2674/23
1/0
2674/5
2674/23
1337/6

result:

ok 9 lines

Test #8:

score: 0
Accepted
time: 1108ms
memory: 9788kb

input:

10 10
1465292 914022939
2258868 101102159
265616 463724951
192430 946841485
2630886 977373286
2016747 443115809
3552227 644307708
3999290 745677354
424627 330625475
2046399 18914556
2263191
3680274
839068
1905778
257097
2496977
3578950
1400222
3781916
2618199

output:

644307708/921341
372838677/159508
644307708/921341
644307708/921341
644307708/921341
644307708/921341
372838677/210170
644307708/921341
124279559/36229
644307708/921341

result:

ok 10 lines

Test #9:

score: 0
Accepted
time: 958ms
memory: 9772kb

input:

10 10
3074356 448776337
2241681 10
3815624 6
2599227 5
2198509 29372688
1850943 1
3863175 588270797
2115696 233002550
2979224 10
3126325 1125164
699495
709378
709923
2237353
2178964
3523938
567329
540819
83920
2664198

output:

448776337/2374861
448776337/2364978
448776337/2364433
448776337/837003
448776337/875847
588270797/339237
448776337/2507027
448776337/2533537
588270797/3779255
588270797/788819

result:

ok 10 lines

Test #10:

score: -100
Wrong Answer
time: 1012ms
memory: 10064kb

input:

100 100
1701033 665952298
3762088 427918742
942820 11367751
2265136 280409781
3945575 817499835
1580704 296571569
3021728 261050042
2200976 533446489
2930927 46397514
3128777 340713103
2466856 779166152
280779 157964999
851989 377722211
1094216 226133388
227570 985055136
3969447 224992764
1453039 24...

output:

955407863/185720
445006427/124838
685780122/237253
445006427/124838
445006427/124838
685780122/237253
955407863/144386
445006427/124838
445006427/124838
439022287/181846
445006427/124838
213959371/52193
445006427/124838
445006427/124838
439022287/181846
445006427/124838
445006427/124838
445006427/12...

result:

wrong answer 1st lines differ - expected: '978266048/116645', found: '955407863/185720'