QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#50794 | #4823. No! | Irisu | WA | 1108ms | 10064kb | C++14 | 2.8kb | 2022-09-29 12:36:57 | 2022-09-29 12:37:00 |
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: 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'