QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#50792 | #4823. No! | Irisu | WA | 478ms | 15864kb | C++14 | 2.5kb | 2022-09-29 12:34:35 | 2022-09-29 12:34:37 |
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))
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 u*o.d<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());
// 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(){
solve();
orzjk::flush();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 7728kb
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: 2ms
memory: 9756kb
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: 2ms
memory: 9816kb
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: 2ms
memory: 9776kb
input:
1 1 8 9 8
output:
1/0
result:
ok single line: '1/0'
Test #5:
score: 0
Accepted
time: 2ms
memory: 9860kb
input:
1 1 3 1 6
output:
1/0
result:
ok single line: '1/0'
Test #6:
score: 0
Accepted
time: 3ms
memory: 9756kb
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: 0ms
memory: 9756kb
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: -100
Wrong Answer
time: 478ms
memory: 15864kb
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:
745677354/1736099 372838677/159508 372838677/1580111 372838677/1046756 745677354/3742193 248559118/500771 372838677/210170 124279559/433178 124279559/36229 745677354/1381091
result:
wrong answer 1st lines differ - expected: '644307708/921341', found: '745677354/1736099'