TLE in Foe Pairs (Educational Codeforces Round 10)

Question

On implementing O(N+M) complexity code for Foe Pairs problem http://codeforces.com/contest/652/problem/C, I am getting TLE in Test Case 12.

Constraint : (1 ≤ N, M ≤ 3·105)

I am not getting, why for this constraint O(N+M) is getting TLE.

Here, is the code

#include<iostream>
#include<vector>

using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    std::vector<int> v(n+1);
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin>>x;
        v[x] = i;
    }
    std::vector<int> dp(n,0);
    for (int i = 0; i < m; ++i)
    {
        int a,b;
        cin>>a>>b;
        if(v[a]>v[b])
            swap(a,b);
        dp[v[b]] = max(dp[v[b]], v[a]+1);
    }
    for (int i = 1; i < n; ++i)
    {
        dp[i] = max(dp[i], dp[i-1]);
    }
    long long s = 0;

    for (int i = 0; i < n; ++i)
    {
        s+=(i+1-dp[i]);
    }
    cout<<s;
}

Is there anything, I am missing?

score 1 · Accepted Answer · edited May 23 '17 at 11:45

I changed all cin to scanf, it passed all test cases : http://codeforces.com/contest/652/submission/17014495

#include<cstdio>
#include<iostream>
#include<vector>

using namespace std;
int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    //cin>>n>>m;
    std::vector<int> v(n+1);
    for (int i = 0; i < n; ++i)
    {
        int x;
        //cin>>x;
        scanf("%d", &x);
        v[x] = i;
    }
    std::vector<int> dp(n,0);
    for (int i = 0; i < m; ++i)
    {
        int a,b;
        //cin>>a>>b;
        scanf("%d%d", &a, &b);
        if(v[a]>v[b])
            swap(a,b);
        dp[v[b]] = max(dp[v[b]], v[a]+1);
    }
    for (int i = 1; i < n; ++i)
    {
        dp[i] = max(dp[i], dp[i-1]);
    }
    long long s = 0;

    for (int i = 0; i < n; ++i)
    {
        s+=(i+1-dp[i]);
    }
    cout<<s;
    return 0;
}

You should always try to use scanf when the amount of input is large as it is faster.

You can read more about scanf being faster here : Using scanf() in C++ programs is faster than using cin?

TLE in Foe Pairs (Educational Codeforces Round 10)

1 Answers1