QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#50799 | #4823. No! | Irisu | TL | 2254ms | 5708kb | C++14 | 2.8kb | 2022-09-29 12:44:18 | 2022-09-29 12:44:19 |
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 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: 0ms
memory: 3640kb
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: 3568kb
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: 3684kb
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: 3644kb
input:
1 1 8 9 8
output:
1/0
result:
ok single line: '1/0'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
1 1 3 1 6
output:
1/0
result:
ok single line: '1/0'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3640kb
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: 3508kb
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: 2254ms
memory: 3672kb
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: 1803ms
memory: 5708kb
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
Time Limit Exceeded
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...