QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408175#4823. No!chenxinyang2006WA 33ms80732kbC++203.1kb2024-05-09 19:29:562024-05-09 19:29:58

Judging History

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

  • [2024-05-09 19:29:58]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:80732kb
  • [2024-05-09 19:29:56]
  • 提交

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],mrk[4000005],idx[500005];

struct frac{
	ll p,q;
	frac(ll _p,ll _q){p = _p;q = _q;}
	frac(){p = q = 0;}
}dp[4000005];
bool operator <(frac s,frac t){
	return s.p * t.q < t.p * s.q;
}
bool operator >(frac s,frac t){
	return s.p * t.q > t.p * s.q;	
}
bool operator ==(frac s,frac t){
	return s.p * t.q == t.p * s.q;	
}
bool operator <=(frac s,frac t){
	return s.p * t.q <= t.p * s.q;
}
frac max(frac s,frac t){
	chkmax(s,t);
	return s;
}
void print(frac s){
	printf("%lld/%lld ",s.p,s.q);
}

void printans(frac s){
	ll d = __gcd(s.p,s.q);
	printf("%lld/%lld\n",s.p / d,s.q / d);
}

struct line{
	ll k,b;
	frac pos;//在 pos 处超过了上一条
	line(ll _k,ll _b,frac _pos){k = _k;b = _b;pos = _pos;}
};

struct hull{
	int op;
	vector <line> sta;

	frac getval(int p){
//		printf("hull %d getval %d\n",op,p);
		int pos = 0;
		per(k,__lg(SZ(sta)),0) if(pos + (1 << k) < SZ(sta) && frac(-sta[pos + (1 << k)].b,sta[pos + (1 << k)].k - p) > frac(-sta[pos + (1 << k) - 1].b,sta[pos + (1 << k) - 1].k - p)) pos += 1 << k;
//		print(frac(-sta[pos].b,sta[pos].k - p));
//		printf("\n");
		return frac(-sta[pos].b,sta[pos].k - p);
	}
	void ins(ll k,ll b){
//		printf("hull %d ins %lld %lld\n",op,k,b);
		while(!sta.empty()){
			frac lim(b - sta.back().b,sta.back().k - k);
			if(lim <= sta.back().pos) sta.pop_back();
			sta.eb(k,b,lim);
			return;
		}
		sta.eb(k,b,frac(0,1));
	}
}P,Q;//P 含 j,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]);
		mrk[idx[i]] = 1;
	}

	dp[m] = {inf,1};
	P.ins(m,-a[m]);
	P.op = 0;Q.op = 1;
	int j = m;
	per(i,m - 1,1){
		if(!a[i] && !mrk[i]){
			dp[i] = dp[i + 1];
			continue;
		}

		while(P.getval(i) < dp[j]){
			if(a[j]) Q.ins(j,-a[j]);
			if(j == i + 1) break;
			j--;
			if(a[j]) P.ins(j,-a[j]);
		}
		if(P.getval(i) > dp[j]) dp[i] = max(dp[j],Q.getval(i));
		else dp[i] = P.getval(i);
	}
//	printf("fin\n");

	rep(i,1,q){
		if(idx[i] >= m) printf("1/0\n");
		else printans(dp[idx[i]]);
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 69912kb

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

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

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

input:

1 1
8 9
8

output:

1/0

result:

ok single line: '1/0'

Test #5:

score: 0
Accepted
time: 3ms
memory: 69932kb

input:

1 1
3 1
6

output:

1/0

result:

ok single line: '1/0'

Test #6:

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

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: 3ms
memory: 68392kb

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: -100
Wrong Answer
time: 33ms
memory: 80732kb

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
488686643/895909
644307708/921341
977373286/2206259
644307708/921341
372838677/210170
644307708/921341
124279559/36229
644307708/921341

result:

wrong answer 3rd lines differ - expected: '644307708/921341', found: '488686643/895909'