QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408174 | #4823. No! | chenxinyang2006 | WA | 0ms | 69360kb | C++20 | 3.1kb | 2024-05-09 19:29:29 | 2024-05-09 19:29:29 |
Judging History
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 '