TLE on every testcase for Matryoshka

Problems and Contests
#1

I’m solving Matryoshka (https://usaco.guide/gold/lis#problem-joi-16-matryoshka) and when I submit (A - マトリョーシカ人形) it TLEs on every testcase (besides REing on a few test cases in subtask 4).

However, I downloaded the test cases (JOI 2015/2016 春季トレーニング合宿　課題) and it returns instantly for at least the small tests (as expected…). Also, I tested it on the testcases that it REs on and it doesn’t RE locally…

What could be the cause of this?

My code for reference:

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;


using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)

template<typename T, unsigned long N>
istream & operator>>(istream& in, array<T, N>& arr) {
    F0R(i, N) cin >> arr[i];
}

using ll = long long;
using ld = long double;

template<typename T>
using vv = vector<vector<T>>;

using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;

using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;

template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;

template<typename T>
using oset = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

const ll M = 1000000007;
const ll infll = M * M;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vii rh(n);
    F0R(i, n) cin >> rh[i];
    sort(all(rh), greater<>());
    vector<array<int, 3>> ab(q);
    F0R(i, q) {
        cin >> ab[i][0] >> ab[i][1];
        ab[i][2] = i;
    }
    sort(all(ab), greater<>());
    int cq = 0;
    vi dp(n+1, M);
    dp[0] = -M;
    vi res(q);
    F0R(i, n) {
        *lower_bound(all(dp), rh[i][1]) = rh[i][1];
        while (cq < q && ab[cq][0] >= rh[i][0]) {
            res[ab[cq][2]] = upper_bound(all(dp), ab[cq][1]) - dp.begin() - 1;
            cq++;
        }
    }
    while (cq < q) {
        res[ab[cq][2]] = upper_bound(all(dp), ab[cq][1]) - dp.begin() - 1;
        cq++;
    }
    F0R(i, q) cout << res[i] << '\n';
}
#2

In general, it’s a good idea to try running your code somewhere else (ex. one of the sites listed here). Running it on USACO Guide IDE TLEs:

https://ide.usaco.guide/MsXwKvrwDYATINfr7p0

Compiling the program with warning options as mentioned here produces the following explanation:

sol.cpp: In function 'std::istream& operator>>(std::istream&, std::array<_Tp, _Nm>&)':
sol.cpp:26:1: warning: no return statement in function returning non-void [-Wreturn-type]
   26 | }
      | ^

I’ll leave you to figure out the rest.

#3

Thanks :man_facepalming: