SPOJ — KQUERY (TLE)

Revision en1, by sajalhsn13, 2017-03-24 11:46:12

KQUERY

How can i optimize my code?

#include <bits/stdc++.h>

using namespace std;

int n, m, a[30005];
int bs;
vector<int> block[300];

int sqrtDecomposition(int l, int r, int v){
        if(l / bs == r / bs){
                int cnt = 0;
                for(int i = l; i <= r; i++){
                        if(a[i] > v) cnt++;
                }
                return cnt;
        }

        int cnt = 0;
        for(int i = l; i / bs == l / bs; i++){
                if(a[i] > v) cnt++;
        }
        for(int i = r; r / bs == i / bs; i--){
                if(a[i] > v) cnt++;
        }
        for(int i = l / bs + 1; i < r / bs; i++){
                cnt += (block[i].end() - upper_bound(block[i].begin(), block[i].end(), v));
        }
        return cnt;
}

int main(){
        cin >> n;
        for(int i = 0; i < n; i++){
                scanf("%d", a + i);
        }
        bs = sqrt(n);
        for(int i = 0; i < n; i++){
                block[i/bs].push_back(a[i]);
        }
        for(int i = 0; i < 300; i++){
                sort(block[i].begin(), block[i].end());
        }
        cin >> m;
        for(int i = 0; i < m; i++){
                int l, r, v;
                scanf("%d %d %d", &l, &r, &v);
                l--; r--;
                int ans = sqrtDecomposition(l, r, v);
                printf("%d\n", ans);
        }
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English sajalhsn13 2017-03-24 11:46:12 1504 Initial revision (published)