0_0_33203904_13536.cpp:2:23: error: stray '#' in program
using namespace std; #define debug(a) cerr<<#a<<" --> "<<(a)<<endl; #define INPUT freopen("input.txt","r",stdin) template<class T1, class T2> ostream &operator <<(ostream &os, pair<T1,T2>&p); template <class T> ostream &operator <<(ostream &os, vector<T>&v); template <class T> ostream &operator <<(ostream &os, set<T>&v); template <class T1, class T2> ostream &operator <<(ostream &os, map<T1,T2>&v); typedef long long ll; const int N = 2000+5; int wa[N],wb[N],wv[N],wc[N]; int r[N],sa[N],rak[N], height[N], lg[N]; void init() { memset(wa,0,sizeof wa); memset(wb,0,sizeof wb); memset(wv,0,sizeof wv); memset(wc,0,sizeof wc); memset(r,0,sizeof r); memset(sa,0,sizeof sa); memset(rak,0,sizeof rak); memset(height,0,sizeof height); } int cmp(int *r,int a,int b,int l) { return r[a] == r[b] && r[a+l] == r[b+l]; } void da(int *r,int *sa,int n,int m) { int i,j,p,*x=wa,*y=wb,*t; for( i=0; i<m; i++) wc[i]=0; for( i=0; i<n; i++) wc[x[i]=r[i]] ++; for( i=1; i<m; i++) wc[i] += wc[i-1]; for( i= n-1; i>=0; i--) sa[--wc[x[i]]] = i; for( j= 1,p=1; p<n; j*=2,m=p) { for(p=0,i=n-j; i<n; i++) y[p++] = i; for(i=0; i<n; i++) if(sa[i] >= j) y[p++] = sa[i] - j; for(i=0; i<n; i++) wv[i] = x[y[i]]; for(i=0; i<m; i++) wc[i] = 0; for(i=0; i<n; i++) wc[wv[i]] ++; for(i=1; i<m; i++) wc[i] += wc[i-1]; for(i=n-1; i>=0; i--) sa[--wc[wv[i]]] = y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]] = 0,i=1; i<n; i++) x[sa[i]]= cmp(y,sa[i-1],sa[i],j) ? p-1:p++; } } void calheight(int *r,int *sa,int n) { int i,j,k=0; for(i=1; i<=n; i++) rak[sa[i]] = i; for(i=0; i<n; height[rak[i++]] = k ) { for(k?k--:0, j=sa[rak[i]-1] ; r[i+k] == r[j+k] ; k ++) ; } } int dp[N][22]; void initRMQ(int n) { for(int i= 1; i<=n; i++) dp[i][0] = height[i]; for(int j= 1; (1<<j) <= n; j ++ ) { for(int i = 1; i + (1<<j) - 1 <= n ; i ++ ) { dp[i][j] = min(dp[i][j-1], dp[i + (1<<(j-1))][j-1]); } } } int askRMQ(int L,int R) { int k = lg[R-L+1]; return min(dp[L][k], dp[R - (1<<k) + 1][k]); } int preclg2() { for(int i=2; i<N; i++) { lg[i]=lg[i-1]; if((i&(i-1))==0) lg[i]++; } } int get_lcp(int i, int j) { int L=min(rak[sa[i]],rak[sa[j]]), R=max(rak[sa[i]],rak[sa[j]]); return askRMQ(L+1,R); } int query(int l,int r, int n) { int prv = 0; int sum =0; for(int i = 1; i <= n; i++) { if(sa[i]>=l) { int p =1, q = r-sa[i]+1; int k = n - sa[i]; int tmp =0; if(prv!=0) { tmp = get_lcp(i,prv); } k-= tmp; if(k > 0) sum += k; prv= i; } } return sum; } vector<int>v[N]; int mp[N][N]; void TEST_CASES(int cas) { vector<pair<int,int> >queries; string s; cin>>s; int sz; sz= s.size(); for(int i=0; i<sz; i++) { v[i].clear(); } int q; scanf("%d",&q); for(int i=0; i<q; i++) { int l, r; scanf("%d %d",&l,&r); l--; r--; queries.push_back({l,r}); v[r].push_back(l); mp[l][r] =0; } int n =sz; for(int j = sz-1; j>=0; j--) { if(v[j].size()) { int cnt =0; for(int i=0; i<n; i++) { r[i]=s[i]-'a'+1; cnt=max(cnt,r[i]); } r[n]=0; da(r,sa,n+1,cnt+1); calheight(r,sa,n); initRMQ(n); for(int it:v[j]) { if(!mp[it][j]) { mp[ it][j] = query(it,j,n); } } } n--; s.pop_back(); } for(int i=0; i<q; i++) { int ans = mp[queries[i].first][queries[i].second]; printf("%d\n",ans); } } int main() { preclg2(); int t=1,cas=0; scanf("%d",&t); while(t--) { TEST_CASES(++cas); } return 0; } template<class T1, class T2> ostream &operator <<(ostream &os, pair<T1,T2>&p) { os<<"{"<<p.first<<", "<<p.second<<"} "; return os; } template <class T> ostream &operator <<(ostream &os, vector<T>&v) { os<<"[ "; for(int i=0; i<v.size(); i++) { os<<v[i]<<" " ; } os<<" ]"; return os; } template <class T> ostream &operator <<(ostream &os, set<T>&v) { os<<"[ "; for(T i:v) { os<<i<<" "; } os<<" ]"; return os; } template <class T1, class T2> ostream &operator <<(ostream &os, map<T1,T2>&v) { for(auto i:v) { os<<"Key : "<<i.first<<" , Value : "<<i.second<<endl; } return os; }
^
0_0_33203904_13536.cpp:2:46: error: stray '#' in program
using namespace std; #define debug(a) cerr<<#a<<" --> "<<(a)<<endl; #define INPUT freopen("input.txt","r",stdin) template<class T1, class T2> ostream &operator <<(ostream &os, pair<T1,T2>&p); template <class T> ostream &operator <<(ostream &os, vector<T>&v); template <class T> ostream &operator <<(ostream &os, set<T>&v); template <class T1, class T2> ostream &operator <<(ostream &os, map<T1,T2>&v); typedef long long ll; const int N = 2000+5; int wa[N],wb[N],wv[N],wc[N]; int r[N],sa[N],rak[N], height[N], lg[N]; void init() { memset(wa,0,sizeof wa); memset(wb,0,sizeof wb); memset(wv,0,sizeof wv); memset(wc,0,sizeof wc); memset(r,0,sizeof r); memset(sa,0,sizeof sa); memset(rak,0,sizeof rak); memset(height,0,sizeof height); } int cmp(int *r,int a,int b,int l) { return r[a] == r[b] && r[a+l] == r[b+l]; } void da(int *r,int *sa,int n,int m) { int i,j,p,*x=wa,*y=wb,*t; for( i=0; i<m; i++) wc[i]=0; for( i=0; i<n; i++) wc[x[i]=r[i]] ++; for( i=1; i<m; i++) wc[i] += wc[i-1]; for( i= n-1; i>=0; i--) sa[--wc[x[i]]] = i; for( j= 1,p=1; p<n; j*=2,m=p) { for(p=0,i=n-j; i<n; i++) y[p++] = i; for(i=0; i<n; i++) if(sa[i] >= j) y[p++] = sa[i] - j; for(i=0; i<n; i++) wv[i] = x[y[i]]; for(i=0; i<m; i++) wc[i] = 0; for(i=0; i<n; i++) wc[wv[i]] ++; for(i=1; i<m; i++) wc[i] += wc[i-1]; for(i=n-1; i>=0; i--) sa[--wc[wv[i]]] = y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]] = 0,i=1; i<n; i++) x[sa[i]]= cmp(y,sa[i-1],sa[i],j) ? p-1:p++; } } void calheight(int *r,int *sa,int n) { int i,j,k=0; for(i=1; i<=n; i++) rak[sa[i]] = i; for(i=0; i<n; height[rak[i++]] = k ) { for(k?k--:0, j=sa[rak[i]-1] ; r[i+k] == r[j+k] ; k ++) ; } } int dp[N][22]; void initRMQ(int n) { for(int i= 1; i<=n; i++) dp[i][0] = height[i]; for(int j= 1; (1<<j) <= n; j ++ ) { for(int i = 1; i + (1<<j) - 1 <= n ; i ++ ) { dp[i][j] = min(dp[i][j-1], dp[i + (1<<(j-1))][j-1]); } } } int askRMQ(int L,int R) { int k = lg[R-L+1]; return min(dp[L][k], dp[R - (1<<k) + 1][k]); } int preclg2() { for(int i=2; i<N; i++) { lg[i]=lg[i-1]; if((i&(i-1))==0) lg[i]++; } } int get_lcp(int i, int j) { int L=min(rak[sa[i]],rak[sa[j]]), R=max(rak[sa[i]],rak[sa[j]]); return askRMQ(L+1,R); } int query(int l,int r, int n) { int prv = 0; int sum =0; for(int i = 1; i <= n; i++) { if(sa[i]>=l) { int p =1, q = r-sa[i]+1; int k = n - sa[i]; int tmp =0; if(prv!=0) { tmp = get_lcp(i,prv); } k-= tmp; if(k > 0) sum += k; prv= i; } } return sum; } vector<int>v[N]; int mp[N][N]; void TEST_CASES(int cas) { vector<pair<int,int> >queries; string s; cin>>s; int sz; sz= s.size(); for(int i=0; i<sz; i++) { v[i].clear(); } int q; scanf("%d",&q); for(int i=0; i<q; i++) { int l, r; scanf("%d %d",&l,&r); l--; r--; queries.push_back({l,r}); v[r].push_back(l); mp[l][r] =0; } int n =sz; for(int j = sz-1; j>=0; j--) { if(v[j].size()) { int cnt =0; for(int i=0; i<n; i++) { r[i]=s[i]-'a'+1; cnt=max(cnt,r[i]); } r[n]=0; da(r,sa,n+1,cnt+1); calheight(r,sa,n); initRMQ(n); for(int it:v[j]) { if(!mp[it][j]) { mp[ it][j] = query(it,j,n); } } } n--; s.pop_back(); } for(int i=0; i<q; i++) { int ans = mp[queries[i].first][queries[i].second]; printf("%d\n",ans); } } int main() { preclg2(); int t=1,cas=0; scanf("%d",&t); while(t--) { TEST_CASES(++cas); } return 0; } template<class T1, class T2> ostream &operator <<(ostream &os, pair<T1,T2>&p) { os<<"{"<<p.first<<", "<<p.second<<"} "; return os; } template <class T> ostream &operator <<(ostream &os, vector<T>&v) { os<<"[ "; for(int i=0; i<v.size(); i++) { os<<v[i]<<" " ; } os<<" ]"; return os; } template <class T> ostream &operator <<(ostream &os, set<T>&v) { os<<"[ "; for(T i:v) { os<<i<<" "; } os<<" ]"; return os; } template <class T1, class T2> ostream &operator <<(ostream &os, map<T1,T2>&v) { for(auto i:v) { os<<"Key : "<<i.first<<" , Value : "<<i.second<<endl; } return os; }
^
0_0_33203904_13536.cpp:2:70: error: stray '#' in program
using namespace std; #define debug(a) cerr<<#a<<" --> "<<(a)<<endl; #
|
