2013年7月5日 星期五

2013/7/5 UVA 12003 - Array Transformer

/* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3154 */
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
bool cmp(int a, int b)
{
    return a < b;
}
int SJ[300000], S[300000];
int main()
{
    int n, m, u; int L, R, v, p;
    while( scanf("%d %d %d", &n, &m, &u) != EOF )
    {
        int sqrt_n = (int)sqrt(n);
       
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &SJ[i]);
            S[i] = SJ[i];
        }
       
        int k;
        for(k = 0; k+2*sqrt_n <= n; k+=sqrt_n)
        {
            sort(S+k, S+k+sqrt_n, cmp);  
        }
        sort(S+k, S+n, cmp);
       
        for(int i = 0; i < m; i++)
        {
            int l, r, cnt;
            scanf("%d %d %d %d", &L, &R, &v, &p);
            L--; R--; p--;cnt = 0;
           
            for(k = 0; k+2*sqrt_n <= n; k+=sqrt_n)
            {
                l = k; r = k + sqrt_n-1;
             
                if( R < l || r < L ){ continue; }
                else if( L <= l && r <= R )
                {
                    if( S[l] >= v ){  }
                    else if( S[r] <  v ){ cnt += sqrt_n; }
                    else
                    {
                        int mid = (l+r)/2;
                        while( l != r-1 )
                        {
                            if( S[mid] < v ){ l = mid; }
                            else{ r = mid; }
                            mid = (l+r)/2;
                        }
                        cnt += r-k;
                    }  
                }
                else
                {
                    int op = min(r,R);
                 
                    for(int j = max(l,L); j <= op; j++)
                    {
                        if(SJ[j] < v){ cnt++; }
                    }
                }
             
            }
            l = k; r = n-1;
            if( R < l || r < L ){}
            else if( L <= l && r <= R )
            {
                if( S[l] >= v ){  }
                else if( S[r] <  v ){ cnt += sqrt_n; }
                else
                {
                    int mid = (l+r)/2;
                    while( l != r-1 )
                    {
                        if( S[mid] < v ){ l = mid; }
                        else{ r = mid; }
                        mid = (l+r)/2;
                    }
                    cnt += r-k;
                }  
            }
            else
            {
                int op = min(r,R);
                for(int j = max(l,L); j <= op; j++)
                {
                    if(SJ[j] < v){ cnt++; }
                }
            }
            SJ[p] = (int)((long long int)u*(long long int)cnt/(long long int)(R-L+1));
           
            for(k = 0; k+2*sqrt_n <= n; k+=sqrt_n)
            {
                l = k; r = k + sqrt_n;
                if( p >= l && p < r )
                {
                    for(int lol = l; lol < r; lol++)
                    {
                        S[lol] = SJ[lol];
                    }  
                    sort(S+l, S+r, cmp);
                }  
            }
            l = k; r = n;
            if( p >= l && p < r )
            {
                for(int lol = l; lol < r; lol++)
                {
                    S[lol] = SJ[lol];
                }  
                sort(S+l, S+r, cmp);
            }
        }
        for(int i = 0; i < n; i++)
        {
            printf("%d\n", SJ[i]);  
        }
   
    }
   
}


沒有留言:

張貼留言