12299

[fR0D]

What is wrong with my code for 12299 - RMQ with Shifts?

Code: Select all

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<string>

using namespace std;

typedef vector<int> VI;

#define REP(i,N) for(int i=0; i<(N); ++i)
#define FOREACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)

#define PB push_back

template<class T>
class SegmentTree
{
     int *A,size;
     public:
     SegmentTree(int N)
     {
          size = 1;
          while(size < N) size *= 2;
          size *= 2;
          size -= 1;
          A = new int[size];
          memset(A,-1,4*size);
     }
     void initialize(int node, int start,int end, T *array)
     {
          if (start==end)
             A[node] = start;
          else
          {
              int mid = (start+end)/2;
              initialize(2*node+1,start,mid,array);
              initialize(2*node+2,mid+1,end,array);
              if (array[A[2*node+1]]<=array[A[2*node+2]])
                 A[node] = A[2 * node + 1];
              else
                  A[node] = A[2 * node + 2];
          }
     }
     void update(int node, T *array) {
         int index = size/2 + node;
         //
         node = (index - 1 ) / 2;
         while( A[2 * node + 1] == -1 || A[2 * node + 2] == -1) node = (node - 1)/2;
         while (node >= 0) {
            if (array[A[2*node+1]]<=array[A[2*node+2]])
                 A[node] = A[2 * node + 1];
                 else
                  A[node] = A[2 * node + 2];
                if(node == 0) break;
                node = (node - 1) / 2;
         }
    }
     int query(int node, int start,
                   int end, int i, int j, T *array)
     {
         int id1,id2;
         if (i>end || j<start)
            return -1;

         if (start>=i && end<=j)
            return A[node];

         int mid = (start+end)/2;
         id1 = query(2*node+1,start,mid,i,j,array);
         id2 = query(2*node+2,mid+1,end,i,j,array);

         if (id1==-1)
            return id2;
         if (id2==-1)
            return id1;

         if (array[id1]<=array[id2])
            return id1;
         else
             return id2;
     }
};

int main()
{
   int n, q, a, b, j, k;
   scanf("%d%d",&n,&q);
   int *A = new int[n];
   REP(i,n) scanf("%d",&A[i]);
   SegmentTree<int> s(n);
   
   s.initialize(0,0,n-1,A);
   char str[100];
   getchar();
   REP(i,q) {
      gets(str);
      if(str[0]=='q') {
         j = 0;
         while(!isdigit(str[j])) j++;
         
         a = str[j] - '0';
         j++;
         while(isdigit(str[j])) {
            a = a * 10 + str[j] - '0';
            ++j;
         }
         
         j++;
         b = str[j] - '0';
         j++;
         while(isdigit(str[j])) {
            b = b * 10 + str[j] - '0';
            ++j;
         }
         printf("%d\n",A[s.query(0,0,n-1,a-1,b-1,A)]);
      }
      else {
         VI ind;
         VI value;
         j = 5;
         while(1) {
            if(str[j] == ')') break;
            j++;
            a = 0;
            while(isdigit(str[j])) {
               a = a * 10 + str[j] - '0';
               ++j;
            }
            ind.PB(a-1);
            value.PB(A[a-1]);
         }
         j = 1;
         k = ind.size();
         FOREACH(it, ind) {
            A[*it] = value[j % k];
            s.update(*it, A);
            ++j;
         }
      }
   }
}