QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#869#579994#9372. Prefix of SuffixestricyzhkxguggFailed.2024-09-21 20:31:102024-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 SuffixesguggTL 53ms9568kbC++201.1kb2024-09-21 19:37:042024-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;
}