Page 1 of 1

12299 - RMQ with Shifts

Posted: Sat Oct 01, 2011 5:46 pm
by 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;
			}
		}
	}
}