QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397293#3749. Use FFTSamponYWAC ✓88ms7892kbC++141.4kb2024-04-23 21:33:212024-04-23 21:33:22

Judging History

This is the latest submission verdict.

  • [2024-04-23 21:33:22]
  • Judged
  • Verdict: AC
  • Time: 88ms
  • Memory: 7892kb
  • [2024-04-23 21:33:21]
  • Submitted

answer

#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 500005
#define P 1000000007
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
  int s = 1;
  while(n) {
    if(n & 1) s = 1ll * s * p % P;
    p = 1ll * p * p % P, n >>= 1;
  }
  return s;
}
int n, m, L, R;
int a[N], b[N];
il int calc(int x) {
  int s = 0;
  FOR(i, 0, min(m, x)) addr(s, 1ll * b[i] * a[min(n, x - i)] % P);
  return s;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  while(cin >> n >> m >> L >> R) {
    FOR(i, 0, n) cin >> a[i], addr(a[i], a[i - 1]);
    FOR(i, 0, m) cin >> b[i];
    cout << add(calc(R), P - calc(L - 1)) << "\n";
  }
  cerr << 1.0 * clock() / CLOCKS_PER_SEC;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 88ms
memory: 7892kb

input:

121 285 293 344
72406343 29062835 764055826 405957571 16850604 195010152 172508328 95932334 831517980 743997761 105129557 514312920 823346977 323074892 692747568 19841766 27687784 347985813 687459437 105444325 409463081 290623333 617535612 772316325 337644791 385678680 277673818 798282616 401321010 ...

output:

844655532
265155792
721082700
495929230
51368183
333395998
317686334
360990019
417166860
777286141
790612844
963001524
160679555
18876664
993526858
577807872
57755040
386940508
941107272
983715250
846414206
784228123
996873567
716573418
156108377
323145621
213071341
252732267
964022445
861123759
102...

result:

ok 1001 numbers