QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#870#579994#9372. Prefix of SuffixestricyzhkxguggSuccess!2024-09-21 20:32:132024-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:


IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#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;
}