oj.uz

Submission #470673

# Submission time Handle Problem Language Result Execution time Memory
470673 2021-09-04T21:40:51 Z Carmel_Ab1 Brperm (RMI20_brperm) C++17
0 / 100
 1824 ms 262148 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;
            }
        }

}

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:27: 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++) {
      |                          ~^~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 2020 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 11 ms 2020 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 1824 ms 262148 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 11 ms 2020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -