I was doing the following question: https://codeforces.net/contest/2044/problem/F
Upon doing this question, I used a method that gives the solution in O(nq) time (about 2 * 10^5 * 5 * 10^4 = 10^10 operations). Code is as follows:
https://codeforces.net/contest/2044/submission/304178376
Spoiler
// #include <bits/stdc++.h>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
// #define INT_MAX 2147483647
// #define INT_MIN -2147483648
#define HAS_TESTCASE 0
bool CHECK_FOR_TESTCASE = false;
bool CHECK_NOW = false;
bool FIRST_TESTCASE = true;
using namespace std;
// For tree, uncomment below
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
template <typename T>
using Tree =
__gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag,
__gnu_pbds::tree_order_statistics_node_update>;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V> void __print(const pair<T, V> &x) {
cerr << '{';
__print(x.first);
cerr << ',';
__print(x.second);
cerr << '}';
}
template <typename T> void __print(const T &x) {
int f = 0;
cerr << '{';
for (auto &i : x)
cerr << (f++ ? "," : ""), __print(i);
cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) {
__print(t);
if (sizeof...(v))
cerr << ", ";
_print(v...);
}
#ifdef LOCAL_PROJECT
#define debug(x...) \
cerr << "[" << #x << "] = ["; \
_print(x)
#else
#define debug(x...)
#endif
typedef long long ll;
typedef unsigned long long ull;
int exp(ll a, ll b, ll mod) {
ll res = 1;
while (b > 0) {
if (b & 1) {
res = res * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return res;
}
int n = 2e5 + 1;
vector<ll> fact(n + 1, 1);
vector<ll> inv(n + 1, 1);
ll mod = 1000000007;
#define MOD 1000000007
ll ncr(int n, int r) {
if (r > n) {
return 0;
}
return fact[n] * inv[r] % mod * inv[n - r] % mod;
}
int add(int a, int b) {
if ((a += b) >= MOD)
a -= MOD;
return a;
}
class DisjointSets {
private:
vector<int> parents;
vector<int> sizes;
public:
DisjointSets(int size) : parents(size), sizes(size, 1) {
for (int i = 0; i < size; i++) {
parents[i] = i;
}
}
/** @return the "representative" node in x's component */
int find(int x) {
return parents[x] == x ? x : (parents[x] = find(parents[x]));
}
/** @return whether the merge changed connectivity */
bool unite(int x, int y) {
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root) {
return false;
}
if (sizes[x_root] < sizes[y_root]) {
swap(x_root, y_root);
}
sizes[x_root] += sizes[y_root];
parents[y_root] = x_root;
return true;
}
/** @return whether x and y are in the same connected component */
bool connected(int x, int y) { return find(x) == find(y); }
int getSize(int x) { return sizes[find(x)]; }
int getNumComponents() {
int count = 0;
for (int i = 0; i < (int)parents.size(); i++) {
if (parents[i] == i) {
count++;
}
}
return count;
}
};
int mul(int a, int b) { return int(1LL * a * b % MOD); }
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<ll> a(n);
vector<ll> b(n);
ll sa = 0;
ll sb = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
sa += a[i];
}
vector<ll> b_freq((2*m) + 5, 0);
for (int i = 0; i < m; i++) {
cin >> b[i];
sb += b[i];
ll temp = b[i];
temp += m;
b_freq[temp]++;
}
ll total = 0;
vector<pair<ll, ll>> temp(n, {0, 0});
for (int i = 0; i < n; i++) {
total += (a[i] * sb);
temp[i].first = (a[i] * sb);
temp[i].second = (sa - a[i]);
}
while (q--) {
ll x;
cin >> x;
x = total - x;
bool isYes = false;
for (int i = 0; i < n; i++) {
ll first = temp[i].first;
ll second = temp[i].second;
if (second == 0) {
if (first == x) {
isYes = true;
break;
}
} else {
if ((x - first) % second == 0) {
ll to_find = (x - first) / second;
to_find+= m;
debug(to_find);
if (to_find <= 2 * m && to_find >= 0) {
if (b_freq[to_find] > 0) {
isYes = true;
break;
}
}
// if (mp.find(to_find) != mp.end()) {
// isYes = true;
// break;
// }
}
}
}
if (isYes)
cout << "YES\n";
else
cout << "NO\n";
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
#ifdef LOCAL_PROJECT
freopen("error.txt", "w", stderr);
#endif
// freopen("haircut.in", "r", stdin);
// freopen("haircut.out", "w", stdout);
if (HAS_TESTCASE) {
int t;
cin >> t;
int T = t;
while (t--) {
// if (t != T - 1) {
// FIRST_TESTCASE = false;
// }
// if (t == (10000 - 1722)) {
// CHECK_NOW = true;
// } else {
// CHECK_NOW = false;
// }
// solve_bruteforce();
solve();
}
} else {
solve();
}
}
However, the official solution is in O(n^2) time, which is about (4 * 10^10 operations). https://codeforces.net/blog/entry/137306
Spoiler
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define int long long
#define vt vector
#define endl "\n"
const int N = 4e5 + 5;
bool apos[N], aneg[N], bpos[N], bneg[N], posspos[N], possneg[N];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m,q;
cin >> n >> m >> q;
vector<int> a(n), b(m);
int asum = 0, bsum = 0;
F0R(i, n) {
cin >> a[i];
asum += a[i];
}
F0R(i, m) {
cin >> b[i];
bsum += b[i];
}
F0R(i, n) {
if(abs(asum-a[i]) < N) {
if(asum-a[i]<0) aneg[a[i]-asum]=true;
else apos[asum-a[i]]=true;
}
}
F0R(i, m) {
if(abs(bsum-b[i]) < N) {
if(bsum-b[i]<0) bneg[b[i]-bsum]=true;
else bpos[bsum-b[i]]=true;
}
}
FOR(i, 1, N) {
FOR(j, 1, N) {
if(i * j > N) break;
if(apos[i]&&bpos[j]) posspos[i*j]=true;
if(apos[i]&&bneg[j]) possneg[i*j]=true;
if(aneg[i]&&bpos[j]) possneg[i*j]=true;
if(aneg[i]&&bneg[j]) posspos[i*j]=true;
}
}
while(q--) {
int x;
cin >> x;
if(x>0) {
if(posspos[x]) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
} else {
if(possneg[-x]) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
}
return 0;
}
My solution, however gives TLE. Why is my solution giving TLE but official is not even though operations are lower?
It is $$$O(n \log n)$$$
Thank you I missed that.