QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#335081 | #4823. No! | do_while_true | WA | 0ms | 17968kb | C++20 | 4.2kb | 2024-02-22 17:04:12 | 2024-02-22 17:04:14 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<assert.h>
#define y1 qingway1
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define dbg(x) cerr << "In the line " << __LINE__ << " the " << #x << " = " << x << '\n'
#define dpi(x,y) cerr << "In the line " << __LINE__ << " the " << #x << " = " << x << "; the " << #y << " = " << y << '\n'
using namespace std;
typedef double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
template<typename T>void cmax(T &x,T y){x=x>y?x:y;}
template<typename T>void cmin(T &x,T y){x=x<y?x:y;}
namespace fastio {
template<int T>
struct fast_io {
char p[T], *p1, *p2, q[T], *q1, *q2;
fast_io() {
p1 = p2 = p;
q1 = q;
q2 = q + T;
}
inline char gc() {
return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
}
inline void pc(char ch) {
if (q1 == q2) {
fwrite(q, 1, T, stdout);
q1 = q;
}
*q1++ = ch;
}
~fast_io() {
fwrite(q, 1, q1 - q, stdout);
}
};
fast_io<12'345'678> io;
int read() {
int r = 0, neg = 1;
char ch;
do {
ch = io.gc();
if (ch == '-')
neg = -1;
} while (ch < 48 || ch > 57);
do r = r * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
return r * neg;
}
void write(int x) {
if (x < 0) io.pc('-'), x = -x;
if (x >= 10) write(x / 10);
io.pc(48 + x % 10);
}
void output(int x, char ch = ' ') {
write(x);
io.pc(ch);
}
}
using fastio::read;
using fastio::output;
ll gcd(ll a,ll b){
return !b?a:gcd(b,a%b);
}
int cmp(pll x,pll y){//x<y
return x.fi*y.se < y.fi*x.se;
}
const int N=2500010;
const int inf=0x7fffffff;
const int V=10000010;
int n,q;
pll a[N],b[N];
pll f[N],ans[N];
struct Edge{
int nxt,fi,se;
}e[N];
int head[N],ent;
int rt,tot;
int p[N],ls[N],rs[N];
pll F(int o,int x){
return mp(a[o].fi-x,a[o].se);
}
void modify(int &x,int l,int r,int q){
if(!x)x=++tot;
if(!p[x]){
p[x]=q;
return ;
}
int mid=(l+r)>>1;
if(cmp(F(q,mid),F(p[x],mid)))swap(p[x],q);
if(cmp(F(q,l),F(p[x],l)))modify(ls[x],l,mid,q);
else if(cmp(F(q,r),F(p[x],r)))modify(rs[x],mid+1,r,q);
}
int query(int x,int l,int r,int v){
if(!x)return 0;
int mid=(l+r)>>1;
int o=p[x],s;
if(v<=mid)s=query(ls[x],l,mid,v);
else s=query(rs[x],mid+1,r,v);
if(!s)return o;
return cmp(F(o,v),F(s,v))?o:s;
}
signed main(){
// assert(freopen("data.in","r",stdin));
// assert(freopen("ex_test3.in","r",stdin));
// assert(freopen("1.out","w",stdout));
n=read();q=read();
for(int i=1;i<=n;i++)a[i].fi=read(),a[i].se=read();
sort(a+1,a+n+1,[](const pll &x,const pll &y){return x.fi==y.fi?x.se>y.se:x.fi<y.fi;});
int m=0;
for(int i=1,j;i<=n;i=j+1){
j=i;
while(j<n&&a[j+1].fi==a[i].fi)++j;
b[++m]=a[i];
}
n=m;for(int i=1;i<=n;i++)a[i]=b[i];
for(int i=1;i<=q;i++){
int x=read();
if(x>=a[n].fi)ans[i]=mp(1,0);
else{
int l=1,r=n,mid,as=0;
while(l<=r){
mid=(l+r)>>1;
if(a[mid].fi>x){
as=mid;
r=mid-1;
}
else l=mid+1;
}
e[++ent]={head[as],x,i};
head[as]=ent;
}
}
// cerr << 1.0*clock()/CLOCKS_PER_SEC << '\n';
for(int i=n;i>=1;i--){
if(i==n)f[i]=mp(inf,1);
else{
int p=query(rt,1,V,a[i].fi);
f[i]=mp(a[p].se,a[p].fi-a[i].fi);
if(cmp(f[p],f[i]))f[i]=f[p];
}
modify(rt,1,V,i);
for(int j=head[i];j;j=e[j].nxt){
int p=query(rt,1,V,e[j].fi);
ans[e[j].se]=mp(a[p].se,a[p].fi-e[j].fi);
if(cmp(f[p],ans[e[j].se]))
ans[e[j].se]=f[p];
}
}
for(int i=1;i<=q;i++){
/*
if(ans[i].se!=0){
ll d=gcd(ans[i].fi,ans[i].se);
ans[i].fi/=d;ans[i].se/=d;
}*/
cout << ans[i].fi << '/' << ans[i].se << '\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 17952kb
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: -100
Wrong Answer
time: 0ms
memory: 17968kb
input:
5 6 10 6 3 7 6 15 7 6 8 15 5 3 9 7 7 9
output:
6/2 6/2 6/1 6/2 6/2 6/1
result:
wrong answer 1st lines differ - expected: '3/1', found: '6/2'