QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#845132 | #1942. Another Substring Query Problem | ASnown | TL | 0ms | 0kb | C++17 | 5.1kb | 2025-01-06 15:03:03 | 2025-01-06 15:03:04 |
Judging History
answer
#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popc(x) (__builtin_popcountll((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
namespace asnown {
using i32=int32_t; using u32=uint32_t;
using i64=int64_t; using u64=uint64_t;
using i128=__int128_t; using u128=__uint128_t; };
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
namespace asnown {
using i64=int64_t;
using u64=uint64_t;
using u128=__uint128_t;
namespace isPrime {
constexpr u64 qpow(u64 a,u64 b,u64 p) {
u64 res=1;
for(;b;b>>=1,a=a*a%p)
if(b&1) res=res*a%p;
return res;
}
constexpr bool checkPrime(u64 p) {
if(p==1) return false;
u64 d=__builtin_ctzll(p-1),s=(p-1)>>d;
for(auto a:{2,3,5,7,11,13,82,373}) {
if(a%p==0) continue;
u64 x=qpow(a,s,p),y=0;
for(int i=0;i<d;i++,x=y) {
y=(u128)x*x%p;
if(y==1&&x!=1&&x!=p-1)
return false;
} if(y!=1) return false;
} return true;
}
}
// gen prime in [L,R)
template<u64 __start=0>
constexpr u64 genPrime(u64 l,u64 r) {
using isPrime::checkPrime;
u64 x=__start^0x113817;
for(char c:__TIME__ __TIMESTAMP__)
x+=c,x^=x<<13,x^=x>>7,x^=x<<17;
while(true) {
x^=x<<13,x^=x>>7,x^=x<<17;
auto y=l+x%(r-l);
if(checkPrime(y)) return y;
} return 0;
}
}
namespace asnown {
constexpr i32 inverse(i32 a,i32 m) { i64 r=1;
for(;a>1;a=m%a) r=r*(m-m/a)%m; return r; }
template<i32 m>
class static_modint {
using mint=static_modint;
public:
constexpr static_modint() : v(0) {}
constexpr static_modint(i32 v) : v(normal(v%m)) {}
constexpr static_modint(u32 v) : v(v%m) {}
constexpr static_modint(i64 v) : v(normal(v%m)) {}
constexpr static_modint(u64 v) : v(v%m) {}
constexpr static_modint(i128 v) : v(normal(v%m)) {}
constexpr static_modint(u128 v) : v(v%m) {}
constexpr u32 normal(i32 v) { if(v>=m) v-=m; return v+((v>>31)&m); }
constexpr u32 val() const { return v; }
constexpr static u32 mod() { return m; }
constexpr explicit operator bool() const { return v; }
constexpr mint inv() const { assert(v!=0); return mint(inverse(v,m)); }
constexpr mint pow(i64 b) const { assert(b>=0);
mint a=*this,res=1; for(;b;b>>=1,a*=a) if(b&1) res*=a; return res; }
constexpr mint operator+() const { return *this; }
constexpr mint operator-() const { return mint()-*this; }
constexpr mint& operator+=(const mint &p) { return v=normal(v+p.v),*this; }
constexpr mint& operator-=(const mint &p) { return v=normal(v-p.v),*this; }
constexpr mint& operator++() { return (*this)+=1; }
constexpr mint& operator--() { return (*this)-=1; }
constexpr mint& operator++(i32) { auto tmp=*this; return ++*this,tmp; }
constexpr mint& operator--(i32) { auto tmp=*this; return --*this,tmp; }
constexpr mint& operator*=(const mint &p) { v=i64(v)*p.v%m; return *this; }
constexpr mint& operator/=(const mint &p) { return *this *= p.inv(); }
constexpr friend mint operator+(const mint &p,const mint &q) { return mint(p)+=q; }
constexpr friend mint operator-(const mint &p,const mint &q) { return mint(p)-=q; }
constexpr friend mint operator*(const mint &p,const mint &q) { return mint(p)*=q; }
constexpr friend mint operator/(const mint &p,const mint &q) { return mint(p)/=q; }
constexpr friend std::istream& operator>>(std::istream &is,mint &a) { i64 v; is>>v; a=v; return is; }
constexpr friend std::ostream& operator<<(std::ostream &os,const mint &a) { os<<a.val(); return os; }
constexpr bool operator==(const mint& p) const { return val()==p.val(); }
constexpr bool operator!=(const mint& p) const { return val()!=p.val(); }
private:
u32 v;
};
using modint998244353=static_modint<998244353>;
using modint107=static_modint<1000000007>;
};
const int P=asnown::genPrime<>(9e8,1e9),B=asnown::genPrime<P>(200,500);
using hint=asnown::static_modint<P>;
const int N = 2e5+25;
int n,Q;
string s;
map<int,int> bot;
map<int,vector<pair<int,int>>> q;
int ans[N];
hint pw[N],h[N];
signed main() {
#ifndef ONLINE_JUDGE
#endif
cin.tie(nullptr)->sync_with_stdio(false);
Solve();
}
void Solve() {
cin>>s,n=s.size(),s=' '+s;
pw[0]=1; for(int i=1;i<=n;i++) pw[i]=pw[i-1]*B;
vector<int> len;
cin>>Q;
for(int i=1;i<=Q;i++) {
string t; int k; cin>>t>>k;
len.emplace_back(t.size());
hint h=0;
for(auto ch:t) h=h*B+ch;
ans[i]=-1;
q[h.val()].emplace_back(k,i);
}
sort(ALL(len)),len.erase(unique(ALL(len)),len.end());
for(int i=1;i<=n;i++) {
h[i]=h[i-1]*B+s[i];
for(auto l:len) if(l<=i) {
hint H=h[i]-h[i-l]*pw[l];
++bot[H.val()];
for(auto [k,id]:q[H.val()])
if(bot[H.val()]==k) ans[id]=i-l+1;
}
}
for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...