oj.uz

Submission #540624

# Submission time Handle Problem Language Result Execution time Memory
540624 2022-03-21T08:58:28 Z Killer2501 Trener (COCI20_trener) C++14
110 / 110
 66 ms 23152 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e3+5;
const int M = 1e5+5;
const int mod = 1e9+7;
const ll base = 327;
const ll inf = 1e15+7;
int c[N], d[N], ans, tong, dp[N], h[N];
int n, m, k;
int a[52][N][52], b[N];
vector<int> adj[N], vi, gr[N];
void add(int& x, int y)
{
    x += y;
    if(x >= mod)x -= mod;
}
struct BIT
{
    int n;
    vector<ll> fe;
    BIT(){}
    void init(int _n)
    {
        n = _n;
        fe.assign(n+1, 0);
    }
    void add(int id, ll x)
    {
        for(; id <= n; id += id & -id)fe[id] += x;
    }
    void add(int l, int r, ll x)
    {
        add(l, x);
        add(r+1, -x);
    }
    ll get(int id)
    {
        ll res = 0;
        for(; id; id -= id & -id)res += fe[id];
        return res;
    }
}L, R;
struct query
{
    int x, y, l, r;
}q[N];
vector<string> s[N];
int get(int i, int j, int l, int r)
{
    return (a[i][j][r]-1ll*a[i][j][l-1]*c[r-l+1]%mod+mod)%mod;
}
void sol()
{
    srand((int)(time(0)));
    cin >> n >> m;
    for(int i = 0; i < 26; i ++)b[i] = rand() % mod;
    c[0] = 1;
    for(int i = 1; i <= n; i ++)c[i] = 1ll*c[i-1]*base%mod;
    for(int i = 1; i <= n; i ++)
    {
        s[i].resize(m);
        for(int j = 0; j < m; j ++)
        {
            cin >> s[i][j];
            for(int p = 1; p <= i; p ++)
                a[i][j][p] = (1ll*a[i][j][p-1]*base+b[s[i][j][p-1]-'a'])%mod;
        }
    }
    map<int, int> mp;
    for(int j = 0; j < m; j ++)++mp[a[1][j][1]];
    for(int i = 2; i <= n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            dp[j] = 0;
            k = a[i][j][i-1];
            if(mp.count(k))add(dp[j], mp[k]);
            k = get(i, j, 2, i);
            if(k == a[i][j][i-1])continue;
            if(mp.count(k))add(dp[j], mp[k]);
        }
        mp.clear();
        for(int j = 0; j < m; j ++)
        {
            k = a[i][j][i];
            mp[k] += dp[j];
            if(mp[k] >= mod)mp[k] -= mod;
        }
        //cout << mp.size() << '\n';
    }
    for(int j = 0; j < m; j ++)add(ans, dp[j]);
    cout << ans;

}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}

Compilation message

trener.cpp: In function 'int main()':
trener.cpp:111:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trener.cpp:112:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 484 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2204 KB Output is correct
2 Correct 5 ms 2212 KB Output is correct
3 Correct 5 ms 2156 KB Output is correct
4 Correct 3 ms 2164 KB Output is correct
5 Correct 5 ms 2132 KB Output is correct
6 Correct 5 ms 2132 KB Output is correct
7 Correct 3 ms 2160 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 484 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 5 ms 2204 KB Output is correct
6 Correct 5 ms 2212 KB Output is correct
7 Correct 5 ms 2156 KB Output is correct
8 Correct 3 ms 2164 KB Output is correct
9 Correct 5 ms 2132 KB Output is correct
10 Correct 5 ms 2132 KB Output is correct
11 Correct 3 ms 2160 KB Output is correct
12 Correct 65 ms 23044 KB Output is correct
13 Correct 66 ms 23020 KB Output is correct
14 Correct 66 ms 22988 KB Output is correct
15 Correct 66 ms 22928 KB Output is correct
16 Correct 36 ms 22924 KB Output is correct
17 Correct 64 ms 23152 KB Output is correct
18 Correct 62 ms 23040 KB Output is correct
19 Correct 61 ms 22920 KB Output is correct
20 Correct 63 ms 22996 KB Output is correct
21 Correct 60 ms 23044 KB Output is correct
22 Correct 38 ms 22900 KB Output is correct