QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#408175 | #4823. No! | chenxinyang2006 | WA | 33ms | 80732kb | C++20 | 3.1kb | 2024-05-09 19:29:56 | 2024-05-09 19:29:58 |
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;
}
詳細信息
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'