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 sajalhsn13 2017-03-24 11:46:12 1504 Initial revision (published)