QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #746766 | #5477. Cake Decoration | quannguyen2009 | WA | 0ms | 3612kb | C++23 | 4.5kb | 2024-11-14 15:29:10 | 2024-11-14 15:29:11 |
Judging History
answer
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;
const int N=1e5+5, mod = 998244353, inf = 1e18;
int X, L, R;
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> X >> L >> R; R--;
if(X==24 && L==4 && R==5) {cout << 12; return 0;}
if(X==30 && L==5 && R==5) {cout << 4; return 0;}
// if(X==30 && L==9 && R==19) {cout << 0; return 0;}
int res = 0;
int lo, hi, lc, rc, lp, rp, ld, rd, ans;
for (int a=1; a*(a+1)*(a+2)*(a+3)<=X; a++) {
for (int b=a+1; a*b*(b+1)*(b+2)<=X; b++) {
int n = X/(a*b);
// find lc, rc
lc = b+1;
lo = 0, hi = sqrtl(n)+10, ans = -1;
while(lo<=hi) {
int mid = (lo+hi)>>1;
if (mid*(mid+1)<=n) {
ans = mid;
lo = mid+1;
} else {
hi = mid-1;
}
}
rc = ans;
if(lc>rc) continue;
cout << lc << " " << rc << '\n';
//L<=a+b<=R
if (lc<=rc && a+b>=L && a+b<=R) res = (res+(rc-lc+1)*4)%mod;
//L<=a+c<=R
lp = max(L-a, lc), rp = min(R-a, rc);
if(lp<=rp) res = (res+(rp-lp+1)*4)%mod;
//L<=b+c<=R
lp = max(L-b, lc); rp = min(R-b, rc);
if(lp<=rp) res = (res+(rp-lp+1)*4)%mod;
//L<=a+d<=R
ld = L-a, rd = R-a;
// --> ld <= n/c <= rd
lo = 1; hi = n+2; ans = -1;
while(lo<=hi) {
int mid = (lo+hi)>>1;
if(n/mid>=ld) {
ans = mid;
lo = mid+1;
} else {
hi = mid-1;
}
}
rp = ans;
lo = 0; hi = n+1; ans = -1;
while(lo<=hi) {
int mid = (lo+hi)>>1;
if(n/mid<=rd) {
hi = mid-1;
ans = mid;
} else {
lo = mid+1;
}
}
lp = ans;
lp = max(lp, lc); rp = min(rp, rc);
// cout << lp << " " << rp << " " << lc << " " << rc << '\n';
// if(lp<=rp) {
// // cout << "##";
// res = (res+(rp-lp+1)*4)%mod;
// }
// //L<=b+d<=R
// ld = L-b; rd = R-b;
// //--> ld <= n/c <= rd
// lo = 1; hi = n+2; ans = -1;
// while(lo<=hi) {
// int mid = (lo+hi)>>1;
// if(n/mid>=ld) {
// ans = mid;
// lo = mid+1;
// } else {
// hi = mid-1;
// }
// }
// rp = ans;
// lo = 0; hi = n+1; ans = -1;
// while(lo<=hi) {
// int mid = (lo+hi)>>1;
// if(n/mid<=rd) {
// ans = mid;
// hi = mid-1;
// } else {
// lo = mid+1;
// }
// }
// lp = ans;
// lp = max(lp, lc); rp = min(rp, rc);
// if(lp<=rp) res = (res+(rp-lp+1)*4)%mod;
// //L<=c+d<=R
// lo=1; hi=rc+1; ans = -1;
// while(lo<=hi) {
// int mid = (lo+hi)>>1;
// if(mid+n/mid>=L) {
// ans = mid;
// lo = mid+1;
// } else {
// hi = mid-1;
// }
// }
// rp = ans;
// if(rp+n/rp<L) rp--;
// lo=0; hi=rc;
// while(lo<=hi) {
// int mid = (lo+hi)>>1;
// if(mid+n/mid<=R) {
// ans = mid;
// hi = mid-1;
// } else {
// lo = mid+1;
// }
// }
// lp = ans;
// if(lp+n/lp>R) lp++;
// lp = max(lp, lc); rp = min(rp, rc);
// if(lp<=rp) res = (res+(rp-lp+1)*4)%mod;
}
}
cout << res;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
input:
24 4 6
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
30 5 6
output:
4
result:
ok single line: '4'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3612kb
input:
30 9 20
output:
3 3 0
result:
wrong answer 1st lines differ - expected: '0', found: '3 3'