Recently I have solved this problem and here is my solution:

int n, target;
vector<int> values;
vector<tuple<int, int, int>> paired_sums;

int main() {
    cin >> n >> target;
    values.resize(n);
    for(int &v: values) {
        scanf("%d", &v);
    }
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            paired_sums.push_back(make_tuple(values[i] + values[j], i, j));
        }
    }
    sort(paired_sums.begin(), paired_sums.end());
    int lo = 0, hi = paired_sums.size() - 1;
    while(lo < hi) {
        int lo_value, lo_i, lo_j;
        int hi_value, hi_i, hi_j;
        tie(lo_value, lo_i, lo_j) = paired_sums[lo];
        tie(hi_value, hi_i, hi_j) = paired_sums[hi];
        if(1LL * lo_value + hi_value > target) {
            hi--;
        }
        else if(1LL * lo_value + hi_value < target) {
            lo++;
        }
        else {
            set<int> indexs;
            indexs.insert(lo_i);
            indexs.insert(lo_j);
            indexs.insert(hi_i);
            indexs.insert(hi_j);
            if(indexs.size() != 4) {
                break;
            }
            else {
                printf("%d %d %d %d", ++lo_i, ++lo_j, ++hi_i, ++hi_j);
                exit(0);
            }
        }
    }
    printf("IMPOSSIBLE");
}

After solving this I have come to realize that my code might not pass one test case. Suppose this paired_sums vector has some values ***** 2 3 3 4 **** (here * means other values). the target value is 6. so 2 + 4 is a potential answer. But if their indexes are not unique my code will say IMPOSSIBLE (breaks from the while loop). however, 3 + 3 is also and a potential answer and if the there indexes are unique my code will fail. But this code is accepted. I wonder how!!! Can anyone explain? Thanks in advance.

Hello everyone,

I am trying to solve this problem. If I can build the LCP array with O(n) complexity I can easily solve it. But building LCP array requires suffix array. I know the O(n*logn*longn) algorithm. But It will give me TLE in this problem. I need the O(n) algorithm to build suffix array. I searched for it and get a paper which is too complex to understand for me. Can anyone give me a simple and well explained tutorial to build suffix array with O(n) time? It will be great help for me.

Thank you.

Hello Everyone,

It was known to me that lookup time in unordered_map is faster than map in C++. When I have to lookup frequent than insertion I should use unordered_map. In this problem I used unordered_map because in my implementation lookup is more frequent than insertion. But I got TLE. In my implementation with map I got accepted. what is wrong here? Any explanation will be helpful.

Thank you.

I am trying to solve this problem. There is a tutorial but for me its not so clear. You can see that I am green. For me the state is [numberOfProgrammer][numberOfLine][maxBug] which is 500*500*500. The tutorial has a solution with state 2*500*500. It is very hard for me to understand the state elimination. Someone please explain the solution so that I(as a green) can understand.

Hello,

I am trying to solve this problem and getting TLE, and I think my code is the best thing I can do. Please help me solve the problem by any efficient idea or optimizing my code:

#include <bits/stdc++.h>

using namespace std;

#define MX 5000005
#define M 100000007
#define LL long long
#define dbg(x) cout<<#x<<" = "<<x<<"\n"

int n;
LL cnt[MX];
int b[MX];

int main(){
    while(cin>>n){
        if(n==0) break;
        memset(b,0,sizeof(b));
        for(int i=n,v=1;i>1;i--,v++){
            cnt[i]=v;
        }
        for(int i=2;i<=n;i++){
            if(b[i]==0){
                for(int j=i*2;j<=n;j+=i){
                    b[j]=1;
                    int t=j;
                    int div=0;
                    while(t%i==0){
                        div++;
                        t/=i;
                    }
                    cnt[i]+=cnt[j]*div;
                }
            }
        }
        LL ans=1;
        for(int i=2;i<=n;i++){
            if(b[i]==0){
                ans=(ans*(cnt[i]+1))%M;
            }
        }
        printf("%lld\n",ans);
    }
}

i don't know what is wrong with my idea. I tried many times but still wrong answer. can anyone tell me what is wrong?

source : http://www.spoj.com/problems/GSS2/

code: https://paste.ofcode.org/32Kc7W5baENjJqs2ckLYFwq

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);
        }
}