oj.uz

Submission #470724

# Submission time Handle Problem Language Result Execution time Memory
470724 2021-09-05T09:16:14 Z Carmel_Ab1 Brperm (RMI20_brperm) C++17
0 / 100
 1833 ms 262144 KB 
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld, ld> pld;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
    os << "[";
    for (int i = 0; i < ll(a.size()); i++) { os << a[i] << ((i != ll(a.size() - 1) ? " " : "")); }
    os << "]\n";
    return os;
}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

#include "brperm.h"
//#include "grader.cpp"
const ll m=1e9+7;

vvl h;
vl pref,pows;

ll calc(ll l,ll r){
    ll ans=pref[r];
    if(l)
        l--,ans=(ans-(pref[l]*pows[r-l])%m)%m;
    ans=(ans+m)%m;
    return ans;
}
void init(int n, const char s[]) {
    vector<string>prv(n);
    pref.resize(n);
    h.resize(n,vl(18));
    pows.resize(n,1);
    for(int i=1; i<n; i++)
        pows[i]=(26*pows[i-1])%m;
    for(int i=0; i<n; i++)
        prv[i]=s[i],h[i][0]=(s[i]-'a'+1)%m;

    for(int i=0; i<n; i++)
        pref[i]=((i?26*pref[i-1]:0)+s[i]-'a'+1)%m;

    for(int j=1; j<18; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            string s1 = prv[i], s2 = prv[i + (1 << (j - 1))];
            prv[i].clear();
            for (int k = 0; k < s1.size(); k++) {
                prv[i] += s1[k];
                prv[i] += s2[k];
                h[i][j] = (26 * h[i][j] + s1[k] - 'a' + 1) % m;
                h[i][j] = (26 * h[i][j] + s2[k] - 'a' + 1) % m;
            }
        }
        for(int i=0; i<n; i++)
            if(prv[i].size()!=(1<<j))
                prv[i].clear();
    }
}

int query(int i, int k) {
    return h[i][k]==calc(i,i+(1<<k)-1);
}
/*
 axxyxxyb
0 3
1 1
0 2
3 2

 */

Compilation message

brperm.cpp: In function 'void init(int, const char*)':
brperm.cpp:70:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for (int k = 0; k < s1.size(); k++) {
      |                             ~~^~~~~~~~~~~
brperm.cpp:78:29: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |             if(prv[i].size()!=(1<<j))
      |                ~~~~~~~~~~~~~^~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 2024 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 2024 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1833 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 2024 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -