QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#869 | #579994 | #9372. Prefix of Suffixes | tricyzhkx | gugg | Failed. | 2024-09-21 20:31:10 | 2024-09-21 20:31:11 |
详细
Extra Test:
Accepted
time: 39ms
memory: 9452kb
input:
300000 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 299622 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 300000 lines
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#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;
}