Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #define TOMOD 1000000007
- using namespace std;
- typedef long long int ll;
- class MappingABC2
- {
- public:
- int countStrings(vector <int> t)
- {
- int i = 0; int N = t.size();
- int n_uniques_fltr[64] = {0}, n_uniques_frtl[64] = {0};
- int last_unique_fltr[64] = {0}, last_unique_frtl[64] = {0}, last_unique = 0;
- int used_fltr[64] = {0}, used_frtl[64] = {0};
- n_uniques_fltr[0] = 1; last_unique_fltr[0] = -1; used_fltr[t[0]] = 1; last_unique = 0;
- for(i = 1;i < N;++i)
- if( used_fltr[t[i]] )
- {
- n_uniques_fltr[i] = n_uniques_fltr[i-1];
- last_unique_fltr[i] = last_unique;
- }
- else
- {
- used_fltr[t[i]] = 1;
- n_uniques_fltr[i] = n_uniques_fltr[i-1] + 1;
- last_unique_fltr[i] = last_unique;
- last_unique = i;
- }
- n_uniques_frtl[N-1] = 1; last_unique_frtl[N-1] = -1; used_frtl[t[N-1]] = 1; last_unique = N-1;
- for(i = N-2;i >= 0;--i)
- if( used[t[i]] )
- {
- n_uniques_frtl[i] = n_uniques_frtl[i+1];
- last_unique_frtl[i] = last_unique;
- }
- else
- {
- used[t[i]] = 1;
- n_uniques_frtl[i] = n_uniques_frtl[i+1] + 1;
- last_unique_frtl[i] = last_unique;
- last_unique = i;
- }
- ll ans = 0;
- for(i = 2;i < N-1;++i)
- if( 1 != n_uniques_fltr[i] && 1 != n_unqiues_frtl[i] )
- {
- int center = t[i];
- int left = 0; bool left_have_center = 0;
- for(left = last_unique_fltr[i];-1 != left;left = last_unique_fltr[left])
- {
- if( center == t[left] )
- continue;
- int le = t[left]; bool right_have_le = 0, right_have_center = 0;
- for(int right = last_unique_frtl[i];-1 != right;right = last_unique_frtl[right])
- if( center == t[right] )
- {
- right_have_center = 1;
- }
- else if( t[right] == le )
- {
- right_have_le = 1;
- }
- ans = (ans + n_unique_frtl[i+1] - right_have_le - right_have_center) % TOMOD;
- }
- }
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement