Why this code isn't TLE?

general
1

I did this code for this UVa Problem. It runs in like 6s on my pc but I got AC on the problem and the UVa OJ says my problem ran in 0.256s although it ran in about 6s in my pc with a 40KB test case file I got from UVa site (I have an amd fx 8350 so I guess it should not be the problem). Does this have to do something with precalculation? I still have doubts about this question I asked before. (note: I guess it takes so long to run because each test case I reset the 1M element vector AdjList)

Here’s the code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cmath>
#include <cassert>

using namespace std;

#define s(T) scanf("%d", &T)
#define sl(T) scanf("%lld", &T);
#define fill(a, val) memset(a,val, sizeof(a))
#define all(x) x.begin(), x.end()
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define REP(i,n) FOR(i,0,n)
#define PB push_back
#define MP make_pair
#define mod 1000000007

typedef long int ll;
typedef vector<long int> vi;
typedef map<long int, long int> mii;
typedef pair<long int, long int> ii;
typedef vector<ii> vii;

int main(int argc, char *argv[]) {

    long int n, m, k, v;
    long int temp;
    vector<vii> AdjList;

    while(scanf("%ld %ld\n", &n, &m) != EOF) {
        AdjList.assign(1000002,vii());
        for(long int i = 0; i < n; i++) {
            scanf("%ld", &temp);
            AdjList[temp].PB(ii(i+1,0));
        }
        for(long int i = 0; i < m; i++) {
            scanf("%ld %ld\n", &k, &v);
            if(!AdjList[v].empty()) {
                vii::iterator j = AdjList[v].begin();
                if(k > AdjList[v].size()) printf("0\n");
                else printf("%ld\n", (j+k-1)->first);
            }
            else
                printf("0\n");
        }
    }
    return 0;
}
2

The PC’s we use generally have 4 or 8 gb ram while the solutions are run on large clusters and total memory size is huge ( would run into 100’s of gb’s i guess).

Speaking from personal experience, i have noticed that programs involving allocation of large amount of memory tend to run faster on online judges than on our PC’s. I guess it is because they can quickly allocate large blocks of memory for your program to run while your operating system will have to free memory and then allocate it to your code.

On the other hand , codes requiring very less memory tend to run faster on my system than on code chef.This is the only possible explanation i can think of.

1 Like