QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#870 | #579994 | #9372. Prefix of Suffixes | tricyzhkx | gugg | Success! | 2024-09-21 20:32:13 | 2024-09-21 20:32:15 |
Details
Extra Test:
Time Limit Exceeded
input:
300000 0 1 1 299999 1 1 299997 1 1 299994 1 1 299990 1 1 299985 1 1 299979 1 1 299972 1 1 299964 1 1 299955 1 1 299945 1 1 299934 1 1 299922 1 1 299909 1 1 299895 1 1 299880 1 1 299864 1 1 299847 1 1 299829 1 1 299810 1 1 299790 1 1 299769 1 1 299747 1 1 299724 1 1 299700 1 1 299675 1 1 299649 1 1 2...
output:
1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210 231 253 276 300 325 351 378 406 435 465 496 528 561 595 630 666 703 741 780 820 861 903 946 990 1035 1081 1128 1176 1225 1275 1326 1378 1431 1485 1540 1596 1653 1711 1770 1830 1891 1953 2016 2080 2145 2211 2278 2346 2415 2485 2556 2628 ...
result:
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#579994 | #9372. Prefix of Suffixes | gugg | TL | 53ms | 9568kb | C++20 | 1.1kb | 2024-09-21 19:37:04 | 2024-09-23 01:36:09 |
answer
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <cmath>
#include <bitset>
#include <cassert>
#include <numeric>
using namespace std;
typedef long long ll;
const int N = 300010;
int n;
int ss[N], a[N], b[N], s[N];
int ne[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++) cin >> ss[i] >> a[i] >> b[i];
ll ans = a[1] * b[1];
cout << ans << '\n';
s[1] = ss[1];
for (int i = 2, j = 0; i <= n; i ++)
{
s[i] = (ss[i] + ans) % n;
while (j && s[i] != s[j + 1]) j = ne[j];
if (s[j + 1] == s[i]) j ++;
ne[i] = j;
int k = i;
ll sum = 0;
while (k) sum += b[i - k + 1], k = ne[k];
ans += sum * a[i];
cout << ans << '\n';
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tt = 1;
// cin >> tt;
while (tt --)
{
solve();
}
return 0;
}