Submission #730068

#	Time	Username	Problem	Language	Result	Execution time	Memory
730068		Andrei_Calota	Sum Zero (RMI20_sumzero)	C++14	61 / 100	561 ms	21932 KiB

sumzero

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;
using int64 = long long;

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

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 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 pos[1 + QMAX];
defSum sumOf[1 + NMAX];
int main()
{
   //ifstream cin ("sumzero.in");
   //ofstream cout ("sumzero.out");

   int n; cin >> n; int64 sum = 0;
   int t = 0; sumOf[++ t] = {0, 0};
   for (int i = 1; i <= n; i ++) {
      int x; cin >> x; sum += x;
      sumOf[++ t] = {sum, i};
   }
   sort (1 + sumOf, 1 + sumOf + t, SumOperator);

   int h = 0;
   for (int i = 1; i < t; i ++)
      if (sumOf[i].value == sumOf[i + 1].value)
        validInt[++ h] = {sumOf[i].pos + 1, sumOf[i + 1].pos};
   sort (1 + validInt, 1 + validInt + h, IntOperator);


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

   int k = 0;
   for (int i = 1; i <= h; i ++) {
      defInt I = validInt[i];
      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; int left;
   for (int i = 1; i <= q; i ++) {
      cin >> left; pos[i] = bSearch (left - 1, k);
      cin >> query[i].right;
   }

   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 ++) {
         if (nextBIT[pos[i]][0] != NONE && validInt[nextBIT[pos[i]][0]].right <= query[i].right) {
           query[i].answer += (1 << bit);
           pos[i] = nextInt[nextBIT[pos[i]][0]];
         }
      }
   }
   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