QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408044#4823. No!chenxinyang2006WA 8ms97632kbC++202.6kb2024-05-09 16:37:402024-05-09 16:37:42

Judging History

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

  • [2024-05-09 16:37:42]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:97632kb
  • [2024-05-09 16:37:40]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,m,q;
int a[4000005],b[4000005],idx[500005];

struct info{
	ll p,q;
	int id;//p/q
	info(ll _p,ll _q,int _id){
		p = _p;q = _q;id = _id;
	}
	info(){p = q = id = 0;}
}res[4000005];
vector <info> sta; 
bool cmp(info pst,int cur){//返回是否是旧的 dp 值更小
	return pst.p * (pst.id - cur) <= a[pst.id] * pst.q;
}

info trans(info pst,int cur){
	if(cmp(pst,cur)) return pst;
	return {a[pst.id],pst.id - cur,0};
}

info cmp2(info s,info t){
	if(s.p * t.q > t.p * s.q) return s;
	return t;
}

void prt(ll sa,ll sb){
	ll d = __gcd(sa,sb);
	printf("%lld/%lld\n",sa / d,sb / d);
}

void prt(info qwq){
	printf("%lldvs%lld\n",qwq.p,qwq.q);
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d%d",&n,&q);
	rep(i,1,n){
		int pos,val;
		scanf("%d%d",&pos,&val);
		chkmax(a[pos],val);
		chkmax(m,pos);
	}
	rep(i,1,q){
		scanf("%d",&idx[i]);
		b[idx[i]] = 1;
	}

//	printf("m=%d\n",m);
	sta.eb(inf,1,m);
	per(i,m - 1,1){
		if(!a[i] && !b[i]) continue;
//		printf("i=%d\n",i);
		int pos = SZ(sta);
		per(k,18,0) if(pos >= (1 << k) && cmp(sta[pos - (1 << k)],i)) pos -= 1 << k;
		if(pos == SZ(sta)) res[i] = trans(sta[pos - 1],i);
		else if(!pos) res[i] = trans(sta[pos],i);
		else res[i] = cmp2(trans(sta[pos],i),trans(sta[pos - 1],i));
/*		if(pos >= 1){
			printf("%lld/%lld id=%d\n",sta[pos - 1].p,sta[pos - 1].q,sta[pos - 1].id);
			prt(trans(sta[pos - 1],i));
		}
		if(pos != SZ(sta)){
			printf("%lld/%lld id=%d\n",sta[pos].p,sta[pos].q,sta[pos].id);
			prt(trans(sta[pos],i));
		}*/
		res[i].id = i;
//		printf("%d %lld/%lld\n",i,res[i].p,res[i].q);
		if(a[i]) sta.eb(res[i]);
	}
	rep(i,1,q){
		if(idx[i] >= m) printf("1/0\n");
		else prt(res[idx[i]].p,res[idx[i]].q);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 97632kb

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: 8ms
memory: 97628kb

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: 97464kb

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: 0ms
memory: 97488kb

input:

1 1
8 9
8

output:

1/0

result:

ok single line: '1/0'

Test #5:

score: 0
Accepted
time: 0ms
memory: 97564kb

input:

1 1
3 1
6

output:

1/0

result:

ok single line: '1/0'

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 97516kb

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'