QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408044 | #4823. No! | chenxinyang2006 | WA | 8ms | 97632kb | C++20 | 2.6kb | 2024-05-09 16:37:40 | 2024-05-09 16:37:42 |
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],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;
}
Details
Tip: Click on the bar to expand more detailed information
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'