MarioYC's blog

SPOJ CPAIR
By MarioYC, 12 years ago, In English

Hi everyone, I'm getting TLE in this problem, I'm trying and offline approach (I was getting RE doing it online), solving only for values of v that are given in the queries, I find the adjacents groups of numbers >= v in O(n) using 2 pointers.

The complexity is O(N x (#different values of v) + QlgQ).

Could someone suggest me an optimization or different approach? Thanks :)

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int a[100000];
long long cont[100001];
long long ans[100000];

struct query{
    int v,a,b,id;
    
    query(){}
    
    bool operator < (query X)const{
        return v < X.v;
    }
}q[100000];

int main(){
    int N,Q;
    
    scanf("%d %d",&N,&Q);
    
    for(int i = 0;i < N;++i)
        scanf("%d",&a[i]);
    
    for(int i = 0;i < Q;++i){
        scanf("%d %d %d",&q[i].v,&q[i].a,&q[i].b);
        q[i].b = min(q[i].b,N);
        q[i].id = i;
    }
    
    sort(q,q + Q);
    
    for(int i = 0;i < Q;){
        int e = i;
        
        while(e < Q && q[e].v == q[i].v) ++e;
        
        int v = q[i].v;
        memset(cont,0,sizeof cont);
        
        for(int j = 0;j < N;){
            if(a[j] < v) ++j;
            else{
                int e2 = j;
                
                while(e2 < N && a[e2] >= v) ++e2;
                
                int m = e2 - j;
                
                for(int k = 1;k <= m;++k)
                    cont[k] += m + 1 - k;
                
                j = e2;
            }
        }
        
        for(int j = 1;j <= N;++j)
            cont[j] += cont[j - 1];
        
        for(int j = i;j < e;++j)
            ans[ q[j].id ] = (q[j].a <= q[j].b? cont[ q[j].b ]- cont[ q[j].a - 1 ] : 0);
        
        i = e;
    }
    
    for(int i = 0;i < Q;++i)
        printf("%lld\n",ans[i]);
    
    return 0;
}
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I came up with somethin using Segment tree and lazy propagation. Hope it passes.

→ Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I've just solved this problem offline with the help of DSU and segment tree, which supports adding of arithmetical progression to interval and get sum on interval. The tree was used to count the number of intervals of particular length.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I thought about it too. But why do you need DSU? Just sort to make events ordered increasingly by v-value and then use this segment tree. Condition that A[k] >= v can be changed to minimum on the interval [i, j] >= v. So, for each i, we can find largest interval that contains i having minimum on it with value A[i]. And this can be calculated in O(N)

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Hm. I haven't thought about that, because merging segments wasn't difficult. And there may be some problems with not counting some segment twice if you just find the largest segment.

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is DSU? Could you give a link for it? Thanks :)

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, once you come up with the idea of merging it becomes really similar to this one.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By the way, there is also a way to solve with BIT which is much faster.

    → Reply