Почему время выполнения этих двух кодов отличается? - PullRequest
Новая
       69

Почему время выполнения этих двух кодов отличается?

0 голосов
/ 03 мая 2020

И снова проблема Subarray - это вопрос серии кодеков DSA. Я просматривал решения и заметил, что выполнение двух абсолютно одинаковых кодов занимает разное время. Вопрос идет так.

Для данного массива возьмем подмассив s. Теперь, учитывая k, объедините s с собой m раз, пока длина не станет хотя бы k. Теперь сортируйте его и найдите k-е наименьшее число. Найдите частоту этого числа, пусть частота будет f. Если f существует в S, подмассив красив. Найдите количество красивых подмассивов.

Ссылка: https://www.codechef.com/problems/SUBPRNJL

Оба используют структуры данных на основе политик, чтобы найти ответ. Код, который получил A C: 

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;
#define pbds tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> 

int main() 
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        long long int c=0;
        int m[2003]={0};
        cin>>n>>k;
        int arr[n];
        for(int i=0;i<n;i++)
        cin>>arr[i];

        for(int i=0;i<n;i++)
        {
            pbds s;
            for(int j=i;j<n;j++)
            {
              int length=j-i+1;
              int x=ceil((double)k/length);
              s.insert({arr[j],++m[arr[j]]});
              int y=ceil(((double)k)/x)-1;
              int X=s.find_by_order(y)->first;
              if(m[m[X]])
              c++;
            }
            memset(m,0,sizeof(m));
            s.clear();
        }
        cout<<c<<"\n";
    }
    return 0;
}

Ссылка на решение: https://www.codechef.com/viewsolution/32600660

И абсолютно аналогичный код с TLE 

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
#define pbds tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>
int main()
{
    int t,n,k;
    cin>>t;
    while(t--){
        cin>>n>>k;

        int v[n],i;
        ll c=0;

        for(i=0;i<n;i++)
        cin>>v[i];

        int m[2003]={0};
        for(i=0;i<n;i++){
            pbds s;
            for(ll j=i;j<n;j++){
                ll len=j-i+1;
                s.insert({v[j],m[v[j]]++});
                ll x=ceil((double)k/len);
                ll y=ceil(((double)k)/x);
                x= s.find_by_order(y-1)->first;
                if(m[m[x]])
                c++;
            }

            memset(m,0,sizeof(m));
            s.clear();
        }
        cout<<c<<"\n";
    }


    return 0;
}

Ссылка на это решение: https://www.codechef.com/viewsolution/32600997

Что вызывает эту разницу? Я понимаю с логикой c, использованной для решения, но я не могу понять, почему первый код работает, а второй - нет. Спасибо за помощь! Я здесь совсем новичок, так что прости мои ошибки.

...