QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408174#4823. No!chenxinyang2006WA 0ms69360kbC++203.1kb2024-05-09 19:29:292024-05-09 19:29:29

Judging History

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

  • [2024-05-09 19:29:29]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:69360kb
  • [2024-05-09 19:29:29]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 69360kb

input:

4 5
3 5
4 3
2 5
6 3
5
2
3
7
2

output:

3/1 
3/1 
3/1 
3/2 
3/2 
3/2 
3/2 
3/3 
3/1 
3/1 
3/3 
3/2 
3/2 
3/2 
3/1
3/2
3/2
1/0
3/2

result:

wrong answer 2nd lines differ - expected: '3/2', found: '3/1 '