QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#868#579994#9372. Prefix of SuffixestricyzhkxguggFailed.2024-09-21 20:30:152024-09-21 20:30:15

详细

Extra Test:

Invalid Input

input:

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 1 1
299...

output:


result:

FAIL Expected EOLN (stdin, line 1)

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;
}