Submission #730048

#	Time	Username	Problem	Language	Result	Execution time	Memory
730048		Andrei_Calota	Sum Zero (RMI20_sumzero)	C++14	61 / 100	1086 ms	18496 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

const int NMAX = 4e5;
const int QMAX = 4e5;
const int LOGMAX = 18;

int input[1 + NMAX];

struct defSum {
   int64 value;
   int pos;
};
bool SumOperator (defSum first, defSum second) {
   if (first.value == second.value)
     return first.pos < second.pos;
   return first.value < second.value;
}

struct defInt {
   int left, right;
};
bool IntOperator (defInt first, defInt second) {
   if (first.left == second.left)
     return first.right < second.right;
   return first.left < second.left;
}

defInt validInt[1 + NMAX];

struct defQuery {
   int left, right;
   int answer;
} query[1 + QMAX];

const int NONE = 0;
int bSearch (int target, int k) {
   int left = 1, right = k; int pos = 0;
   while (left <= right) {
      int mid = left + (right - left) / 2;
      if (validInt[mid].left > target) {
        pos = mid;
        right = mid - 1;
      }
      else
        left = mid + 1;
   }
   return pos;
}

int nextInt[1 + NMAX];
const int INPAIR = 2;
int nextBIT[1 + NMAX][INPAIR];

void getBIT (int finalBIT, int k) {
   for (int i = 1; i <= k; i ++)
      nextBIT[i][0] = i;
   for (int bit = 1; bit <= finalBIT; bit ++) {
      for (int i = 1; i <= k; i ++)
         nextBIT[i][1] = nextBIT[nextInt[nextBIT[i][0]]][0];
      for (int i = 1; i <= k; i ++)
         nextBIT[i][0] = nextBIT[i][1];
   }
}

int main()
{
   //ifstream cin ("sumzero.in");
   //ofstream cout ("sumzero.out");

   int n; cin >> n;
   for (int i = 1; i <= n; i ++)
      cin >> input[i];


   vector<defSum> sumOf; sumOf.push_back ({0, 0});
   int64 sum = 0;
   for (int i = 1; i <= n; i ++) {
      sum += input[i];
      sumOf.push_back ({sum, i});
   }
   sort (sumOf.begin (), sumOf.end (), SumOperator);
   int t = sumOf.size ();

   vector<defInt> intervals;
   for (int i = 0; i < t - 1; i ++)
      if (sumOf[i].value == sumOf[i + 1].value)
        intervals.push_back ({sumOf[i].pos + 1, sumOf[i + 1].pos});
   sort (intervals.begin (), intervals.end (), IntOperator);


   /**for (auto I : intervals)
      cout << I.left << " " << I.right << endl;
   cout << endl;**/

   int k = 0;
   for (auto I : intervals) {
      while (k && validInt[k].right >= I.right)
         k --;
      validInt[++ k] = I;
   }

   /**for (int i = 1; i <= k; i ++)
      cout << validInt[i].left << " " << validInt[i].right << endl;**/

   int q; cin >> q;
   for (int i = 1; i <= q; i ++) {
      cin >> query[i].left >> query[i].right;
      query[i].answer = 0;
   }

   for (int i = 1; i <= k; i ++)
       nextInt[i] = bSearch (validInt[i].right, k);

   /**for (int i = 1; i <= k; i ++)
      cout << nextInt[i] << " ";
   cout << endl;**/

   for (int bit = LOGMAX; bit >= 0; bit --) {
      getBIT (bit, k);

      for (int i = 1; i <= q; i ++) {
         int pos = bSearch (query[i].left - 1, k);
         if (nextBIT[pos][0] != NONE && validInt[nextBIT[pos][0]].right <= query[i].right) {
           query[i].answer += (1 << bit);
           query[i].left = validInt[nextBIT[pos][0]].right + 1;
         }
      }
   }
   for (int i = 1; i <= q; i ++)
      cout << query[i].answer << "\n";
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 0 / 39