QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#746478 | #9631. Median Replacement | Nightsky | WA | 2ms | 3700kb | C++14 | 3.1kb | 2024-11-14 14:46:30 | 2024-11-14 14:46:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair <int, int> pii;
inline int read() {
int x = 0, f = 0;
char c = getchar();
while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f? -x : x;
}
const int MAXN = 300;
const int Mod = 1e9+7;
int l[MAXN + 10], r[MAXN + 10];
int DP(int n, int x) {
static int dp[MAXN + 10][2][2];
dp[0][0][0] = 1;
int res = 1;
for (int i = 1; i <= n; ++i) {
int p1 = x - l[i], p2 = r[i] - x + 1;
p1 = max(p1, 0ll); p1 = min(p1, r[i] - l[i] + 1);
p2 = max(p2, 0ll); p2 = min(p2, r[i] - l[i] + 1);
res = 1ll * res * (r[i] - l[i] + 1) % Mod;
dp[i][0][0] = 1ll * (dp[i - 1][1][0] + dp[i - 1][0][0]) * p1 % Mod;
dp[i][1][0] = 1ll * dp[i - 1][0][1] * p1 % Mod;
dp[i][0][1] = 1ll * dp[i - 1][0][0] * p2 % Mod;
}
int sum = ((dp[n][0][0] + dp[n][0][1]) % Mod + dp[n][1][0]) % Mod;
//assert(res >= sum);
return (res - sum + Mod) % Mod;
}
inline int fastpow(int x, int p) {
int ans = 1;
while (p) {
if (p & 1) ans = 1ll * ans * x % Mod;
x = 1ll * x * x % Mod;
p >>= 1;
}
return ans;
}
int Lan(int *X, int *Y, int n, int k) {
int ans = 0;
for (int i = 1; i <= n; ++i) {
int res = 1, prod = 1;
for (int j = 1; j <= n; ++j)
{
if(i == j) continue;
prod = 1ll * prod * (X[i] - X[j]) % Mod, res = 1ll * res * (k - X[j]) % Mod;
}
if(prod < 0) prod += Mod;
if(res < 0) res += Mod;
prod = fastpow(prod, Mod - 2);
ans = (ans + 1ll * res * Y[i] % Mod * prod ) % Mod;
}
if (ans < 0) ans += Mod;
return ans;
}
signed main() {
// freopen ("std.in", "r", stdin);
// freopen ("std.out", "w", stdout);
int T = read();
while (T--) {
int n = read();
for (int i = 1; i <= n; ++i) l[i] = read();
for (int i = 1; i <= n; ++i) r[i] = read();
static int b[MAXN + 10], tot = 0;
for (int i = 1; i <= n; ++i) b[++tot] = l[i];
for (int i = 1; i <= n; ++i) b[++tot] = r[i] + 1;
b[++tot] = 1;
sort(b + 1, b + tot + 1);
tot = unique(b + 1, b + tot + 1) - b - 1;
int ans = 0;
for (int i = 1; i < tot; ++i) {
int L = b[i], R = b[i + 1] - 1;
int len = min(R - L + 1, n + 2);
static int X[MAXN + 10], Y[MAXN + 10];
for (int j = 1; j <= len; ++j) {
X[j] = L + j - 1;
Y[j] = DP(n, X[j]);
}
for (int j = 2; j <= len; ++j)
Y[j] = (Y[j - 1] + Y[j]) % Mod;
if (len == R - L + 1) {
ans = (ans + Y[len]) % Mod;
}
else {
ans = (ans + Lan(X, Y, len, R)) % Mod;
ans = (ans + Mod) % Mod;
}
}
cout << ans << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
10 5 5 1 4 3 2 14 2 5 3 2 5 4 5 1 2 3 13 7 1 2 3 5 5 2 5 3 1 10 2 12 3 2 5 5 5 3 1 5 57 5 3 1 5 5 2 2 3 3 5 4 5 4 4 5 5 4 5 3 5 3 13 7 3 5 3 5 5 1 4 2 3 14 3 4 2 3 5 1 2 5 4 5 2 8 5 7 5 5 1 1 3 5 1 8 2 3 8 1 5 4 4 4 2 3 5 10 5 2 3
output:
180 170 650 265 182 173 120 296 192 131
result:
ok 10 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
10 5 1 2 2 5 3 6 4 2 6 3 5 4 4 1 4 3 6 7 2 5 3 5 5 3 4 2 4 5 7 5 2 6 5 1 5 3 5 2 7 7 3 5 2 5 1 3 3 2 2 10 5 3 2 2 5 4 4 4 5 3 4 11 9 5 3 5 5 3 2 1 3 13 5 2 1 5 5 5 4 1 2 5 10 6 1 2 5 5 3 5 3 4 2 5 9 3 5 2 5 1 1 3 2 1 7 3 3 3 1
output:
120 230 144 110 110 289 324 89 140 122
result:
ok 10 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
10 5 3 1 3 4 4 9 1 3 10 4 5 1 1 3 1 1 9 1 3 3 1 5 5 1 2 3 1 74 1 2 3 1 5 2 5 5 3 4 5 6 8 3 4 5 2 1 3 4 5 2 4 6 4 5 5 2 4 2 1 3 2 11 3 2 3 5 1 5 4 4 2 1 14 6 6 2 5 4 1 3 5 1 9 2 4 5 1 5 4 1 2 4 4 6 1 6 4 4 5 3 2 5 3 5 8 8 5 3 5
output:
196 76 140 172 72 80 486 84 65 224
result:
ok 10 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
10 5 676437428 903889545 700650370 965758082 146716866 676437431 903889567 700650370 965758082 146716866 5 517457740 64600397 388618400 783268973 388618400 517457797 64600397 388618400 783268973 388618400 5 971452763 106948541 259878781 537741075 9504353 971452780 106948544 259878781 537741075 95043...
output:
157838571 539867046 711272106 123881231 497944943 9791579 539012259 963879245 315607794 495624077
result:
ok 10 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
10 5 462008700 417744555 925098328 70231697 547596413 462008735 417744555 925098328 70231697 547596413 5 294230630 403894618 294230635 403894620 403894617 294230638 403894620 294230635 403894620 403894617 5 757647830 757647826 757647828 184694646 161891480 757647839 757647827 757647830 184694646 161...
output:
713470735 905154643 458869425 477055327 633375786 349097981 980046476 478461437 573246310 810688575
result:
ok 10 lines
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 3700kb
input:
10 150 7 1 8 8 2 3 8 2 1 3 2 10 9 7 3 9 4 5 4 5 10 7 9 9 9 3 4 7 10 8 5 3 5 1 8 4 1 2 7 9 10 9 1 7 4 7 6 8 7 6 6 7 4 5 10 8 7 10 2 8 1 4 9 2 9 3 9 6 2 2 7 7 10 8 4 10 4 1 7 3 3 5 4 3 9 7 4 1 8 1 4 4 2 7 5 4 9 6 5 8 6 4 8 7 4 6 8 8 2 9 8 3 10 9 2 4 6 10 2 8 9 1 6 6 7 8 8 7 8 8 8 3 4 6 3 8 10 10 10 3 ...
output:
8640 991535207 997019207 997989587 997260335 997366607 997702727 990119687 990774407 991778991
result:
wrong answer 2nd lines differ - expected: '8000', found: '991535207'