QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#335081#4823. No!do_while_trueWA 0ms17968kbC++204.2kb2024-02-22 17:04:122024-02-22 17:04:14

Judging History

你现在查看的是最新测评结果

  • [2024-02-22 17:04:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:17968kb
  • [2024-02-22 17:04:12]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'