Блог пользователя AshToady

Автор AshToady, история, 3 года назад, По-английски

Considering everything i could find on maps, unordered maps are supposed to be faster than maps. I experimented on a cses problem, and surprisingly unordered map gave TLE on a few test cases whereas map passed them all.

problem

Code

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
#define int long long
 main()
{
     ios_base::sync_with_stdio(false);
    cin.tie(NULL);
int n,x;cin>>n>>x;int a[n+1];

 for(int i=1;i<=n;cin>>a[i++]);
  a[0]=0;
  unordered_map<int,int>mp;
  for(int i=1;i<=n;i++)
  {
    a[i]+=a[i-1];mp[a[i]]++;
  }
  mp[0]++;
  int cnt=0;

  for(int i=n;i>0;i--)
  {  mp[a[i]]--;
      cnt+=mp[a[i]-x];

    //cnt+=k;
    //cout<<it1-a<<it-a<<endl;
  }
cout<<cnt;
}
  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится