fork download
copy 
  1.     #include <bits/stdc++.h>
  2.     #include <chrono>
  3.     using namespace std;
  4.     using namespace chrono;
  5.     // "AJEET JAIN"----"JAI JINENDRA"  
  6.     /* "णमो अरिहंताणं",
  7.         "णमो सिद्धाणं",
  8.         "णमो आयरियाणं",
  9.         "णमो उवज्झायाणं",
  10.         "णमो लोए सव्वसाहूणं",
  11.         "",
  12.         "एसो पंच नमोक्कारो, सव्व पावप्पणासणो",
  13.         "मंगलाणं च सव्वेसिं, पडमं हवै मंगलं",   */
  14.  
  15.  
  16.     // Aliases to op
  17.     using ll = long long;
  18.     using ull = unsigned long long;
  19.     using ld = double;
  20.     using vll = vector<ll>;
  21.  
  22.  
  23.     // Constants
  24.     constexpr ll INF = 4e18;
  25.     constexpr ld EPS = 1e-9;
  26.     constexpr ll MOD = 1e9 + 7;
  27.  
  28.  
  29.  
  30.     // Macros
  31.     #define F first
  32.     #define S second
  33.     #define all(x) begin(x), end(x)
  34.     #define allr(x) rbegin(x), rend(x)
  35.     #define py cout<<"YES\n";
  36.     #define pn cout<<"NO\n";
  37.     #define forn(i,n) for(int i=0;i<n;i++)
  38.     #define for1(i,n) for(int i=1;i<=n;i++)
  39.  
  40.     // #define insert push_back
  41.     #define pb push_back
  42.     #define MP make_pair
  43.     #define endl '\n'
  44.  
  45.     /*
  46.       remove substring or subarray ---> try to think about sliding w
  47.     
  48.     */                  
  49.  
  50.      /*
  51.       
  52.      Golden Rule
  53.  
  54.      1) problem is easy
  55.      2) proofs is easy
  56.      3) implementation is easy
  57.      
  58.      /*
  59.          ROUGH --
  60.          cnt the subaary whose sum = k
  61.          calcult prefix sum of the array
  62.          pre[j] - pre[i - 1] == k ( 1 <= r , l <= n)
  63.          pre[j] - k = pre[i - 1];
  64.                  
  65.      */
  66.  
  67.   void AJNJ(){
  68.     ll n, k;
  69.     cin >> n >> k;
  70.  
  71.     vector<ll> b(n + 1);
  72.     for(int i = 1; i <= n; i++){
  73.         cin >> b[i];
  74.     }
  75.  
  76.     vector<ll> pre(n + 1, 0);
  77.     map<ll, ll> mp, mp1;
  78.  
  79.     mp[0] = 0;      // FIXED
  80.     mp1[0] = 0;
  81.  
  82.     for(int i = 1; i <= n; i++){
  83.         pre[i] = pre[i - 1] + b[i];
  84.  
  85.         if(mp.find(pre[i]) == mp.end()){
  86.             mp[pre[i]] = i;   // first occurrence
  87.         }
  88.         mp1[pre[i]] = i;      // last occurrence
  89.     }
  90.  
  91.     ll maxi = INT_MIN;
  92.     ll mini = INT_MAX;
  93.  
  94.     for(int j = n; j >= 1; j--){
  95.         if(mp.find(pre[j] - k) != mp.end()){
  96.             maxi = max(maxi, j - mp[pre[j] - k]);
  97.         }
  98.         if(mp1.find(pre[j] - k) != mp1.end()){
  99.             mini = min(mini, j - mp1[pre[j] - k]);
  100.         }
  101.     }
  102.  
  103.     if(maxi == INT_MIN) maxi = -1;
  104.     if(mini == INT_MAX) mini = -1;
  105.  
  106.     cout << maxi << " " << mini << endl;
  107. }
  108.  
  109.  
  110.  
  111.     int main(){
  112.         ios::sync_with_stdio(0);
  113.         cin.tie(0);
  114.         cout.tie(0);
  115.         int T = 1;
  116.         cin>>T;
  117.         auto start1 = high_resolution_clock::now();
  118.         while(T--){
  119.             AJNJ();
  120.         }
  121.         auto stop1 = high_resolution_clock::now();
  122.         auto duration = duration_cast<microseconds>(stop1 - start1);
  123.         cerr << "Time: " << duration . count() / 1000 << " ms" << endl;
  124.  
  125.         return 0;
  126.     }
Success #stdin #stdout #stderr 0.01s 5264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1 -1
stderr
copy 
Time: 0 ms
https://ideone.com/Tg06iB
language:
C++14 (clang 8.0)
created:
21 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!