My issue
Please help me for optimization of it’s time complexity
My code
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_map;
#define fastio() ios_base::sync_with_stdio(false), cin.tie(NULL);
#define mod 1000000007
#define pb push_back
#define F first
#define S second
#define sz(x) (int)(x).size()
#define inp(v) for(auto &x: v) cin>>x;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end());
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define repl(i, a, b) for (ll i = a; i < (b); ++i)
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
#define PI 3.1415926535897932384626433832795
#define int8 __int128
#define cb(x) cbrt(x)
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vl = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vpll = vector<pair<ll,ll>>;
const long long INF=1e18;
const long long MM=998244353;
class UnionFind{
private:vector<int>p,rank;
public:
UnionFind(int n){
rank.assign(n,0);p.assign(n,0);
iota(p.begin(),p.end(),0);
}
int findset(int i){return (p[i]==i?i:findset(p[i]));}
bool isSameSet(int i,int j){return findset(i)==findset(j);}
void unionSet(int i,int j){
if(!isSameSet(i,j)){
int parx=findset(i),pary=findset(j);
if(rank[parx]>rank[pary])p[pary]=parx;
else{
p[parx]=pary;
if(rank[parx]==rank[pary])rank[pary]++;
}
}
}
};
ll power( ll N, ll M){
ll power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum =(sum* power)%mod;}
power = (power * power)%mod;M = M >> 1;}
return sum;
}
inline ll inv(ll a, ll p = mod-2){
return power(a,p);
}
inline ll lsb(ll x){
return x&(~(x-1));
}
ll gcd(ll a, ll b){
if (a == 0 or b == 0)return a ^ b;
return gcd(b, a % b);
}
ll lcm2(ll a,ll b){return (a*b)/(__gcd(a,b));}
ll gcd2(ll a,ll b){return __gcd(a,b);}
ll ceil2(ll a,ll b){return (a+b-1)/b;}
const int MAXN = 2 * 1e5 + 5;
vl fact(MAXN), invFact(MAXN);
void precompute() {
fact[0] = invFact[0] = 1;
for (int i = 1; i < MAXN; i++) {
fact[i] = (fact[i - 1] *1LL* i) % mod;
invFact[i] = power(fact[i],mod - 2);
}
}
ll comb(int n, int r) {
if (r > n || r < 0) return 0;
return fact[n] * invFact[r] % mod * invFact[n - r] % mod;
}
const int N = int(1e7) + 10;
vector<bool> prime(N, true);
void precomputeprime(){
for (int i = 2; i < N; i++) {
if (prime[i]) {
for (int j = i + i; j < N; j += i) {
prime[j] = false;
}
}
}
}
ll solve(vl arr,ll x,ll n){
ll sum=0,len=0;
repl(i,0,n){
if( arr[i]==x)len++;
else{
sum+=(len*(len+1))/2;
len=0;
}
}
if(len>=1) sum+=(len*(len+1))/2;
return sum;
}
int main(){
fastio()
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
vl arr(n);
repl(i,0,n)cin>>arr[i];
ll sum1=solve(arr,1,n)+solve(arr,3,n);
unordered_map<ll,ll>map1,map2;
map1[0]=1,map2[0]=1;
ll ans1=0,ans2=0,cnt1=0,cnt2=0;
repl(i,0,n){
ans1+=(arr[i]-2);
cnt1+=map1[ans1];
map1[ans1]++;
if(arr[i]==2){
map2.clear();
map2[0]=1;
ans2=0;
}else{
ans2+=(arr[i]-2);
cnt2+=map2[ans2];
map2[ans2]++;
}
}
cout<<cnt1-cnt2+sum1<<endl;
}
return 0;
}
Problem Link: Normal is Good Practice Coding Problem