QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#50790 | #4823. No! | Irisu | WA | 4ms | 5780kb | C++14 | 2.6kb | 2022-09-29 12:24:27 | 2022-09-29 12:24:29 |
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){
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);
}
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(){
// 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: 5604kb
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: 0ms
memory: 5688kb
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: 3ms
memory: 5588kb
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: 4ms
memory: 5536kb
input:
1 1 8 9 8
output:
1/0
result:
ok single line: '1/0'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
1 1 3 1 6
output:
1/0
result:
ok single line: '1/0'
Test #6:
score: -100
Wrong Answer
time: 3ms
memory: 5780kb
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:
3/8 58/7 3/8 3/4 3/8 3/8 3/8 29/1 3/8
result:
wrong answer 1st lines differ - expected: '191/37', found: '3/8'