Problem Link: Problem - E - Codeforces
My code for this problem is as follows
//#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <tuple>
#include <numeric>
#include <climits>
#include <bitset>
#include <iomanip>
#include <random>
#include <ctime>
using namespace std;
//change the long long to int if you need to save memory/time really badly
typedef int ll;
//Comment this define when working on interactive problems
#define endl "\n"
#define sqrt(n) sqrt((long double) n)
const ll MAXN = 5e5 + 5;
const ll ZER = 0;
const ll ONE = 1;
const ll INF = LLONG_MAX;
const ll MOD = 998244353;
ll min(ll a, ll b) {
if (a < b) {
return a;
} else {
return b;
}
}
ll max(ll a, ll b) {
if (a > b) {
return a;
} else {
return b;
}
}
ll mod(ll num) {
return (num >= MOD ? num % MOD : num);
}
void solve(ll ca)
{
ll n; cin >> n;
ll a[n], b[n];
for (ll i = 0; i < n; i++) {
cin >> a[i];
}
for (ll i = 0; i < n; i++) {
cin >> b[i];
}
ll ps[n+2];
for (ll i = 0; i < n+2; i++) {
ps[i] = 0;
}
ll needed = 0;
for (ll i = 0; i < n; i++) {
if (a[i] <= b[i]) {
continue;
}
needed++;
vector<pair<ll, ll>> v1, v2;
//These 2 for loops should run in logn time due to harmonic sequences
for (ll j = 1; j <= n; ) {
ll val = (a[i]+j-1)/j;
if (val == 1) {
v1.push_back({val, n-j+1});
break;
}
ll val2 = (a[i]+val-2)/(val-1);
v1.push_back({val, val2-j});
j = val2;
}
for (ll j = 1; j <= n; ) {
ll val = (b[i]+j-1)/j;
if (val == 1) {
v2.push_back({val, n-j+1});
break;
}
ll val2 = (b[i]+val-2)/(val-1);
v2.push_back({val, val2-j});
j = val2;
}
ll lef = 0; ll ri = 0; ll cnt1 = 0; ll cnt2 = 0;
while (lef < v1.size() && ri < v2.size()) {
if (v1[lef].first == v2[ri].first) {
ll x1 = max(cnt1+1, cnt2+1);
ll y1 = min(cnt1+v1[lef].second, cnt2+v2[ri].second);
if (x1 <= y1) {
ps[x1]++;
ps[y1+1]--;
}
cnt1+=v1[lef].second;
cnt2+=v2[ri].second;
lef++; ri++;
} else if (v1[lef].first < v2[ri].first) {
cnt2+=v2[ri].second;
ri++;
} else {
cnt1+=v1[lef].second;
lef++;
}
}
}
for (ll i = 1; i <= n+1; i++) {
ps[i] += ps[i-1];
}
vector<ll> ans;
for (ll i = 1; i <= n; i++) {
if (ps[i] == needed) {
ans.push_back(i);
}
}
cout << ans.size() << endl;
for (auto el: ans) {
cout << el << " ";
}
cout << endl;
return;
}
int main()
{
mt19937 rng(0);
//Fast IO
ios::sync_with_stdio(false);
cin.tie(nullptr);
/*
freopen("sabotage.in", "r", stdin);
freopen("sabotage.out", "w", stdout);
*/
ll t = 1;
cin >> t;
ll co = 1;
while (t--) {
solve(co);
++co;
}
}
I’ve calculated the time complexity to be around O(nlogn), as there is one outer loop that runs n times. Inside the loop, I have 3 smaller loops that run in around O(logn) time. Does anyone know why this code TLE’s?
Edit: Nevermind, the smaller loops don’t run in logn