We apologize for the delay in editorial of the tasks.
Idea: _HossamYehia_
Tutorial
Tutorial is loading...
Solution(_HossamYehia_)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
#endif
int t;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i = 0 ; i < n ; ++i)
scanf("%d", a + i);
sort(a, a + n);
if(a[0] == a[n - 1]){
printf("%lld\n", (1LL * n * (n - 1LL)));
continue;
}
int mn = 0, mx = n - 1;
while(a[0] == a[mn])
++mn;
while(a[n - 1] == a[mx])
--mx;
long long l = mn;
long long r = n - mx - 1;
printf("%lld\n", 2LL * l * r);
}
}
Idea: _HossamYehia_
Tutorial
Tutorial is loading...
Solution(_HossamYehia_)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 1e5 + 5, M = 1e5 + 5;
int n, m;
int mn[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
#endif
int t;
scanf("%d", &t);
while(t--){
scanf("%d %d", &n, &m);
for(int i = 1 ; i <= n ; ++i)
mn[i] = n;
for(int i = 0 ; i < m ; ++i){
int x, y;
scanf("%d %d", &x, &y);
if(x > y)
swap(x, y);
mn[x] = min(mn[x], y - 1);
}
for(int i = n - 1 ; i ; --i)
mn[i] = min(mn[i], mn[i + 1]);
ll ans = n;
for(int i = 0 ; i < n ; ++i)
ans += (mn[i] - i);
printf("%lld\n", ans);
}
}
Idea: _HossamYehia_
Tutorial
Tutorial is loading...
Solution(_HossamYehia_)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 2 * N + 5;
bool vis[N], ans;
void Sieve(){
memset(vis, true, sizeof(vis));
vis[0] = vis[1] = false;
for(int i = 4 ; i < N ; i += 2)
vis[i] = false;
for(int i = 3 ; i < N / i ; i += 2){
if(!vis[i])continue;
for(int j = i * i ; j < N ; j += i + i)
vis[j] = false;
}
}
int in[N], vid;
vector<int> primes;
void Gen(){
for(int i = 2 ; i < N ; ++i)
if(vis[i])
primes.emplace_back(i);
}
set<int> st;
void check(int x){
if(in[x] == vid){
ans = true;
return;
}
in[x] = vid;
}
void fact(int x){
if(x < N && vis[x] == true){
check(x);
return;
}
int idx = 0, sz = primes.size();
while(x > 1 && idx < sz && x / primes[idx] >= primes[idx]){
if(x % primes[idx] == 0){
check(primes[idx]);
while(x % primes[idx] == 0)x /= primes[idx];
}
++idx;
}
if(x > 1){
if(x < N)
return check(x), void();
if(st.find(x) != st.end()){
ans = true;
return;
}
st.emplace(x);
}
}
void pre(){
++vid;
st.clear();
}
int main(){
Sieve();
Gen();
int t;
scanf("%d", &t);
while(t--){
pre();
int n;
scanf("%d", &n);
ans = false;
while(n--){
int x;
scanf("%d", &x);
fact(x);
}
puts(ans ? "YES" : "NO");
}
}
D. Hossam and (sub-)palindromic tree
Idea: 4qqqq
Tutorial
Tutorial is loading...
Solution(4qqqq)
#include <bits/stdc++.h>
using namespace std;
void dfs(int v, vector<vector<int>> &g, vector<vector<int>> &go, vector<vector<pair<int, int>>> &kek, int s, int t = -1, int p = -1, int len = 0){
if(len == 1)
t = v;
if(len > 1)
go[s][v] = t;
kek[len].push_back({s, v});
for(int u : g[v])
if(u != p)
dfs(u, g, go, kek, s, t, v, len + 1);
}
void Solve(){
int n; cin >> n;
string a; cin >> a;
vector<vector<int>> g(n);
vector<vector<int>> go(n, vector<int>(n));
vector<vector<pair<int, int>>> kek(n);
vector<vector<int>> dp(n, vector<int>(n));
for(int i = 0; i < n - 1; i++){
int v, u;
cin >> v >> u;
g[--v].push_back(--u);
g[u].push_back(v);
}
for(int v = 0; v < n; v++)
dfs(v, g, go, kek, v);
for(int len = 0; len < n; len++){
for(auto p : kek[len]){
int v = p.first;
int u = p.second;
if(len == 0){
dp[v][u] = 1;
}else if(len == 1){
dp[v][u] = 1 + (a[v] == a[u]);
}else{
int x = dp[v][go[u][v]];
int y = dp[go[v][u]][u];
int z = dp[go[v][u]][go[u][v]] + ((a[v] == a[u]) << 1);
dp[v][u] = max({x, y, z});
}
}
}
int ans = 0;
for(int v = 0; v < n; v++)
for(int u = 0; u < n; u++)
ans = max(ans, dp[v][u]);
cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
int test = 1;
cin >> test;
for(int i = 1; i <= test; i++)
Solve();
}
Idea: _HossamYehia_
Tutorial
Tutorial is loading...
Solution(_HossamYehia_)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 4e2 + 5;
int n, m;
char a[N][N];
int upM[N][N];
int upB[N][N];
int downM[N][N];
int downB[N][N];
int _get(int I, int j, int incI, char ch){
int i = I + incI;
while(i >= 0 && i < n){
if(a[i][j] == '#')
break;
if(a[i][j] == ch)
break;
i += incI;
}
return i;
}
int _getCount(int i, int j){
if(a[i][j] == 'm')
return 1;
return (a[i][j] == '.' ? 0 : 10);
}
/**
1 2 4 8
UL DL UR DR
*/
int getU(int i, int j, int bt){
if(!bt)
return max(upM[i][j], upB[i][j]) + 1;
int cur = upM[i][j];
if(cur == -1 || a[cur][j] == '#')
return cur + 1;
cur = upM[cur][j];
return cur + 1;
}
int getD(int i, int j, int bt){
if(!bt)
return min(downM[i][j], downB[i][j]) — 1;
int cur = downM[i][j];
if(cur == n || a[cur][j] == '#')
return cur - 1;
cur = downM[cur][j];
return cur - 1;
}
int solve(int i, int l, int r, int msk){
int upL = getU(i, l, (msk & 1));
int downL = getD(i, l, (msk & 2));
int upR = getU(i, r, (msk & 4));
int downR = getD(i, r, (msk & 8));
int up = max(upL, upR);
int down = min(downL, downR);
if(up < i && down > i)
return 2 * (down - up + 1) + (r - l - 1);
return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
#endif
scanf("%d %d", &n, &m);
for(int i = 0 ; i < n ; ++i)
scanf("%s", a + i);
for(int i = 0 ; i < n ; ++i){
for(int j = 0 ; j < m ; ++j){
if(a[i][j] == '#')
continue;
upM[i][j] = _get(i, j, -1, 'm');
upB[i][j] = _get(i, j, -1, '#');
downM[i][j] = _get(i, j, 1, 'm');
downB[i][j] = _get(i, j, 1, '#');
}
}
int mx = 0;
for(int i = 0 ; i < n ; ++i){
for(int j = 0 ; j + 2 < m ; ++j){
int cnt = _getCount(i, j) + _getCount(i, j + 1);
for(int k = j + 2 ; k < m ; ++k){
if((cnt += _getCount(i, k)) > 1)
break;
mx = max(mx, solve(i, j, k, 0));
if(cnt == 1)
continue;
mx = max(mx, solve(i, j, k, 1));
mx = max(mx, solve(i, j, k, 2));
mx = max(mx, solve(i, j, k, 4));
mx = max(mx, solve(i, j, k, 8));
}
}
}
printf("%d\n", mx);
}
F. Hossam and Range Minimum Query
Idea: 4qqqq
Tutorial
Tutorial is loading...
Solution(4qqqq, trie)
#include <bits/stdc++.h>
using namespace std;
const int p1 = 31;
const int p2 = 53;
unsigned long long pow1[32];
unsigned long long pow2[32];
struct Node{
unsigned long long hsh = 0;
Node *l = 0, *r = 0;
bool was = false;
};
const int max_memory = 13e7;
int pos_memory = 0;
char memory[max_memory];
void* operator new(size_t n) {
char *res = memory + pos_memory;
pos_memory += n;
assert(pos_memory <= max_memory);
return (void*) res;
}
void operator delete(void *){}
Node * upd(Node *v, unsigned long long x, int i = 18){
if(i == -1){
Node *u = new Node();
if(!v || v && !v->was){
u->hsh = ((int(1e9) + 345) ^ x) * (3 * x + 654);
u->was = true;
}
return u;
}
if(x & (1 << i)){
Node *res = new Node();
res->l = (v ? v->l : 0);
res->r = upd((v ? v->r : 0), x, i - 1);
unsigned long long a = (res->l ? res->l->hsh * pow1[i + 1] : 0);
unsigned long long b = (res->r ? res->r->hsh * pow2[i + 1] : 0);
res->hsh = a + b;
return res;
}else{
Node *res = new Node();
res->l = upd((v ? v->l : 0), x, i - 1);
res->r = (v ? v->r : 0);
unsigned long long a = (res->l ? res->l->hsh * pow1[i + 1] : 0);
unsigned long long b = (res->r ? res->r->hsh * pow2[i + 1] : 0);
res->hsh = a + b;
return res;
}
}
int get(Node *l, Node *r, int i = 18, int now = 0){
if((l ? l->hsh : 0) == (r ? r->hsh : 0))
return -1;
if(i == -1)
return now;
if((l && l->l ? l->l->hsh : 0) == (r && r->l ? r->l->hsh : 0))
return get((l ? l->r : 0), (r ? r->r : 0), i - 1, now + (1 << i));
return get((l ? l->l : 0), (r ? r->l : 0), i - 1, now);
}
void Solve(){
pow1[0] = 1;
pow2[0] = 1;
for(int i = 1; i <= 31; i++){
pow1[i] = p1 * pow1[i - 1];
pow2[i] = p2 * pow2[i - 1];
}
int n; cin >> n;
vector<pair<int, int>> a(n);
vector<int> mp(n + 1);
{
for(int i = 0; i < n; i++){
cin >> a[i].first;
a[i].second = i;
}
sort(a.begin(), a.end());
map<int, int> kek;
int now = 0;
for(int i = 0; i < n; i++){
if(a[i].first != (i ? a[i - 1].first : -1))
now++;
kek[a[i].first] = now;
}
sort(a.begin(), a.end(), [](pair<int, int> x, pair<int, int> y){ return x.second < y.second; });
for(int i = 0; i < n; i++){
int x = kek[a[i].first];
mp[x] = a[i].first;
a[i].first = x;
}
}
vector<Node *> t(n + 1);
t[0] = new Node();
for(int i = 1; i <= n; i++){
int x = a[i - 1].first;
t[i] = upd(t[i - 1], x);
}
int q; cin >> q;
int last = 0;
while(q--){
int a, b;
cin >> a >> b;
int l = (last ^ a);
int r = (last ^ b);
int kek = get(t[l - 1], t[r]);
int ans = (kek != -1 ? mp[kek] : 0);
cout << ans << '\n';
last = ans;
}
}
signed main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
Solve();
}
Solution(Aleks5d, bitset)
#pragma optimize("SEX_ON_THE_BEACH")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("unroll-all-loops")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
//#define _FORTIFY_SOURCE 0
#pragma GCC optimize("no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include<bits/stdc++.h>
#include <x86intrin.h>
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long int;
using dd = double;
using ldd = long double;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using pdd = std::pair<dd, dd>;
using pld = std::pair<ldd, ldd>;
namespace fast {
template<typename T>
T gcd(T a, T b) {
return gcd(a, b);
}
template<>
unsigned int gcd<unsigned int>(unsigned int u, unsigned int v) {
int shift;
if (u == 0)
return v;
if (v == 0)
return u;
shift = __builtin_ctz(u | v);
u >>= __builtin_ctz(u);
do {
unsigned int m;
v >>= __builtin_ctz(v);
v -= u;
m = (int)v >> 31;
u += v & m;
v = (v + m) ^ m;
} while (v != 0);
return u << shift;
}
template<>
unsigned long long gcd<unsigned long long>(unsigned long long u, unsigned long long v) {
int shift;
if (u == 0)
return v;
if (v == 0)
return u;
shift = __builtin_ctzll(u | v);
u >>= __builtin_ctzll(u);
do {
unsigned long long m;
v >>= __builtin_ctzll(v);
v -= u;
m = (long long)v >> 63;
u += v & m;
v = (v + m) ^ m;
} while (v != 0);
return u << shift;
}
}
namespace someUsefull {
template<typename T1, typename T2>
inline void checkMin(T1& a, T2 b) {
if (a > b)
a = b;
}
template<typename T1, typename T2>
inline void checkMax(T1& a, T2 b) {
if (a < b)
a = b;
}
template<typename T1, typename T2>
inline bool checkMinRes(T1& a, T2 b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<typename T1, typename T2>
inline bool checkMaxRes(T1& a, T2 b) {
if (a < b) {
a = b;
return true;
}
return false;
}
}
namespace operators {
template<typename T1, typename T2>
std::istream& operator>>(std::istream& in, std::pair<T1, T2>& x) {
in >> x.first >> x.second;
return in;
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, std::pair<T1, T2> x) {
out << x.first << " " << x.second;
return out;
}
template<typename T1>
std::istream& operator>>(std::istream& in, std::vector<T1>& x) {
for (auto& i : x) in >> i;
return in;
}
template<typename T1>
std::ostream& operator<<(std::ostream& out, std::vector<T1>& x) {
for (auto& i : x) out << i << " ";
return out;
}
}
//name spaces
using namespace std;
using namespace operators;
using namespace someUsefull;
//end of name spaces
//defines
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define NO {cout << "NO"; return;}
#define YES {cout << "YES"; return;}
//end of defines
//#undef HOME
//debug defines
#ifdef HOME
#define debug(x) cerr << #x << " " << (x) << endl;
#define debug_v(x) {cerr << #x << " "; for (auto ioi : x) cerr << ioi << " "; cerr << endl;}
#define debug_vp(x) {cerr << #x << " "; for (auto ioi : x) cerr << '[' << ioi.ff << " " << ioi.ss << ']'; cerr << endl;}
#define debug_v_v(x) {cerr << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cerr << ioi2 << " "; cerr << '\n';} cerr << "*/" << #x << endl;}
int jjj;
#define wait() cin >> jjj;
#define PO cerr << "POMELO" << endl;
#define OL cerr << "OLIVA" << endl;
#define gen_clock(x) cerr << "Clock " << #x << " created" << endl; ll x = clock();
#define check_clock(x) cerr << "Time spent in " << #x << ": " << clock() - x << endl; x = clock();
#define reset_clock(x) x = clock();
#define say(x) cerr << x << endl;
#else
#define debug(x) 0;
#define debug_v(x) 0;
#define debug_vp(x) 0;
#define debug_v_v(x) 0;
#define wait() 0;
#define PO 0;
#define OL 0;
#define gen_clock(x) 0;
#define check_clock(x) 0;
#define reset_clock(x) 0;
#define say(x) 0;
#endif // HOME
const int SIZE = 200000;
const int block = 64;
const int _size = (SIZE + 63) / 64;
struct bs {
ull arr[_size];
bs() {
for (int i = 0; i < _size; ++i) arr[i] = 0;
}
bs& operator^=(bs &other) {
#pragma GCC ivdep
for (int i = 0; i < _size; ++i)
arr[i] ^= other.arr[i];
return *this;
}
int _Find_first_in_xor(bs& other) {
ull t;
for (int i = 0; i < _size; ++i) {
if (t = arr[i] ^ other.arr[i]) {
return (i << 6) + __builtin_ctzll(t);
}
}
return SIZE;
}
int _Find_first() {
for (int i = 0; i < _size; ++i) {
if (arr[i]) {
return (i << 6) + __builtin_ctzll(arr[i]);
}
}
return SIZE;
}
void flip(int id) {
ull &x = arr[id >> 6];
id &= 63;
x ^= ((ull)1 << id);
}
int size() {
return SIZE;
}
};
ostream& operator<<(ostream &os, bs &x) {
for (int i = 0; i < _size; ++i) {
os << x.arr[i] << " ";
}
return os;
}
void solve(int test) {
int n;
cin >> n;
vector<int> arr(n);
cin >> arr;
vector<int> to(n);
{
map<int, int> have;
for (int i : arr) have[i] = 0;
int cnt = 0;
for (auto &i : have) {
i.ss = cnt;
to[cnt] = i.ff;
cnt++;
}
for (int &i: arr) i = have[i];
}
vector<vector<int>> blocks;
for (int i = 0; i < n; i += block) {
blocks.push_back({});
for (int j = 0; i + j < n && j < block; ++j) {
blocks.back().push_back(arr[i + j]);
}
}
vector<bs> blocks_bs(blocks.size());
for (int i = 0; i < blocks.size(); ++i) {
for (int j : blocks[i]) {
blocks_bs[i].flip(j);
}
}
for (int i = 1; i < blocks.size(); ++i) {
blocks_bs[i] ^= blocks_bs[i - 1];
}
int q;
cin >> q;
bs have;
int last = 0;
for (int i = 0; i < q; ++i) {
int a, b;
cin >> a >> b;
int l = (last ^ a);
int r = (last ^ b);
// cin >> l >> r;
--l;
--r;
int lb = l / block;
int rb = r / block;
if (rb - lb <= 1) {
int L = l;
while (l <= r) {
have.flip(arr[l]);
++l;
}
int id = have._Find_first();
int ans = (id == have.size() ? 0 : to[id]);
last = ans;
cout << ans << '\n';
l = L;
while (l <= r) {
have.flip(arr[l]);
++l;
}
} else {
int L = (lb + 1) * block;
int old_l = l;
int R = (rb + 1) * block;
checkMin(R, n);
int old_r = r;
++r;
while (r < R) {
blocks_bs[rb].flip(arr[r]);
++r;
}
while (l < L) {
blocks_bs[lb].flip(arr[l]);
++l;
}
int id = blocks_bs[rb]._Find_first_in_xor(blocks_bs[lb]);
int ans = (id == have.size() ? 0 : to[id]);
last = ans;
cout << ans << '\n';
r = old_r;
++r;
while (r < R) {
blocks_bs[rb].flip(arr[r]);
++r;
}
l = old_l;
while (l < L) {
blocks_bs[lb].flip(arr[l]);
++l;
}
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
//freopen("file.in", "r", stdin);
//freopen("file.out", "w", stdout);
int t = 1;
//cin >> t;
for (int i = 0; i < t; ++i) {
solve(i+1);
//cout << '\n';
//PO;
}
return 0;
}
/*
*/
Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).
Thanks for the lightning fast editorial.
We are so sorry for long tutorial :(
We are so sorry for it. Our friend _HossamYehia_ is sick, so he couldn't write editorial fast.
Bro no problem, I was just kidding, we knew there must be some issues, otherwise editorials comes out soon.
Anyways, I hope _HossamYehia_ recovers soon!
Thanks for the editorial.
Thanks for the editorials.
Thanks a lot.
video Editorial for Chinese: bilibili
Great
Waited for educational #139 rating update, and then rating of #837 "temporarily" (maybe permanently) rolled back
Is the algorithm in problem C really fast enough? I implemented that in Python (with pre-computed prime list and still got TLE for test case 3.
Similarly, an n^2 algorithm in Python TLEed in case 15 for D.
I understand C++ is the major language for CP but it was a bit unfair.
even cpp takes 2.8 seconds for me. scary, and I don't think my implementation is particularly terrible, i tried improving it as well. it still stays around 2.7 seconds
If you take a look at my previouscomment you will find that problem C accepted in pypy3 but TLE in pypy3 64bit .
- The constraints of problem C is very tight even for c++ ,I saw many c++ solutions took above 2s to execute and maybe got TLE!
Thank you for the reply. I did see comments like that in the contest thread, I just want to raise the issue again after the official ‘expected solution’ is published…
I was able to make the algorithm pass by multiplying two numbers at a time then factoring the larger number.
F can be solved by persistent segment tree + xor hash with a very straightforward thought.
can you explain to me ?
Suppose that $$$hs$$$ is a hash function. After compressing the elements, let the $$$j$$$th leaf of the $$$i$$$th segment tree store $$$hs(j)$$$ if $$$j$$$ has occured an odd number of times up to index $$$i$$$, and $$$0$$$ otherwise, and store in each node the XOR of its children.
For each query, we can binary search on the $$$l-1$$$ th and $$$r$$$ th segment trees for the leftmost leaf that has different values, which is the answer we seek.
Yep, that's true. But editorial of F is already long, so i decided dont add third solution here.
I think you have flipped the statements in point C, p divides a_i and a_j rather than a_i and a_j divide p
Worth waiting for the editorial, very clear and smooth explanation for C and D
After rating of #837 rolled back my rating become 1607->1640 lol
Perhaps too many cheaters removed??
Who else need this mind blowing OPTIMIZER ?
Everything makes sense with the trie until the part where scary hashes came in. I'll present a solution with a persistent trie (which is a persistent segtree) and xor hashing.
Imagine if we took the xor of all the elements in the range $$$arr[l \dots r]$$$. The final result we would get would be the xor of all the numbers that occur an odd number of times. So now imagine we took the xor of all the elements in the range $$$arr[l \dots r]$$$ that are also $$$\leq v$$$ for some $$$v$$$. Again, we would get the xor of all the elements $$$\leq v$$$ that occur an odd number of times. We need to find the smallest value $$$v$$$ such that this xor sum is nonzero. Hey, that is binary search!
There are two problems with this approach so far.
1) It is possible to accidentally get a xor of $$$0$$$ with some elements that each occur an odd number of times. For instance, $$$1 \oplus 2 \oplus 3 = 0$$$ but none of them occur an even number of times.
2) How do we even check this binary search?
Let's tackle problem 2 first.
Our check function is checking if the xor of all the numbers in the range $$$arr[l \dots r]$$$ that are also $$$\leq v$$$ is nonzero. We can break this sum up into two prefix sums of $$$arr[1 \dots r] \oplus arr[1 \dots l]$$$.
Imagine we had infinite time and memory to precompute something that lets us find the xor of all the elements from $$$arr[1 \dots i]$$$ that are $$$\leq v$$$ for some $$$v$$$. For instance, if we had a $$$n$$$ implicit segtrees (or tries) where on $$$st[i][j]$$$ we stored the total xor of all $$$arr[k]$$$ where $$$arr[k] = j$$$ and $$$k \leq i$$$. A check would be a query from $$$(0, v)$$$ on $$$st[l-1]$$$ xored with a query from $$$(0, v)$$$ on $$$st[r]$$$.
We, unfortunately, do not have infinite memory, we can notice that $$$st[i]$$$ and $$$st[i-1]$$$ differ by very little. This leads us to think about persistent segtrees. We can make N versions of a segtree where in each version we xor $$$st[i][arr[i]]$$$ with $$$arr[i]$$$.
This now gives us an $$$O(n \log n + q \log^2 n)$$$ solution since we are binary searching for 1 log and querying the persistent segtree to check for a second log. I don't know if this can pass, but we can improve queries to only be $$$\log n$$$.
Walking on segtree is a special case of binary search where each query only relies on information aggregated in the segtree instead of a segtree query. Each segtree node corresponds to a range $$$[lo \dots hi]$$$; we want to find the leaf node that corresponds to the answer where on each step we can go the left or the right child. If the two left children of versions l-1 and r have a nonzero xor, we know the answer is the left children; otherwise, it is with the right children. Now since checking is $$$O(1)$$$, the complexity is $$$O(n \log n + q \log n)$$$.
Now for the first problem, we have to avoid collisions. We can assign each value a random hash from $$$[0, 2^{60})$$$ such that if $$$arr[i] < arr[j]$$$, $$$hash[arr[i]] < hash[arr[j]]$$$ and use much larger implicit segtrees. This makes query/update time $$$\log MAX$$$ where $$$MAX$$$ is the max hash value used. For the math behind collisions, Odd Mineral Resource (1479D)'s editorial is nice. The final complexity is $$$O(n \log MAX + q \log MAX)$$$. My submission can be found here.
Thanks mate. Very useful :) .
What's the proof of the complexity for problem C?
https://en.wikipedia.org/wiki/Prime-counting_function The number of prime numbers less than n are of the order of n/log(n)
Dear _HossamYehia_, Are you sure problem C is $O(n \times \frac{\sqrt A}{\log A})$?There is a set inside your code.
you can use unordered_set. My solution do it. Sorry, tutorial was written by me :( But Hossam solution is fast enough.
can someone help me with Problem C? I am getting TLE, though I used the same algorithm as in the editorial to solve the problem. Link to my submission : https://codeforces.me/contest/1771/submission/185215774
I tried to find a problem. Sadly, I couldn't. I can just give you some general tips how to speed up your code. A must-have is fast IO: ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); This unsyncs cin and cout, which makes the code faster. However, you must remove it on interactive problems, and you mustn't use "endl", use '\n' instead.
Also there are such things as pragmas. They usually also speed up, however they don't work on some platforms. I use these: pragma GCC optimize("O3,unroll-loops") pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") They start with symbol #, just as include does
Thank you for the tips.
On some compiler " pragma GCC optimize("O3,unroll-loops") pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") " Give error as I have previously asked a drought Spoj. How to fight these types of questions with tight constraints? I was calculating prime till 1e5 getting TLE. I change it to 35000, and it passes.
Don't use unorder_map if the number less than 1e7 or 1e6.Replace with an array, just like the std.
Why is my code getting TLE in problem C? Can someone help me to optimize it? 185388869
Problem E is really simple. For each point, determine how far up/down it can go before encountering a yellow, and how far up/down it can go if it encounters exactly one yellow (this isn't that hard).
Then, simply bash out all possible middle lengths, and you get the answer relatively easily.
Code:184788266
In bitset solution of F what does the line
#pragma optimize("SEX_ON_THE_BEACH")
do?it teases you to ask about it
it's my good luck charm :)
With the kind of problems like F you can easily just request to print $$$ans_q$$$, it is just as hard.
Why is 185759665 this code passing and 185759576 this code giving TLE verdict.
Can anyone please help me understand editorial of prblm C in details with examples ? I can't understand the editorial
For D2C it sounds pretty much like "so, just brute force it"
Fast enough if you use c++
100k * 30k / 30 = 1e8 division operations
For others it made it pretty much unsolvable unless they do some heavy optimizations and use sophisticated methods.
Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).
Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).
Hey everyone. In problem C, if we are calculating prime numbers $$$\le \sqrt{A}$$$, why isn't the time complexity $$$O(n\cdot\frac{\sqrt{A}}{\log{\sqrt{A}}})$$$?
Ref: https://en.wikipedia.org/wiki/Prime_number_theorem#Statement
Edit: Never mind. It wouldn't matter because that would effectively become $$$O(2\cdot n\cdot\frac{\sqrt{A}}{\log{A}})$$$
Isn't problem D too standard? (the Longest Palindromic Subsequence DP can be easily searchable).
F is subproblem of this problem
My submition 198457835 get MLE in test 15. There are no STL or struct or any possible thing which will lead to MLE. I only use 16M for normal c++ array(something like : int dp[2000][2000]) please someone help me, i've tried everything i can come up with but failed.
sorry i just find out i give a too small array for the edge,but still don't understand why it is mle but re
.
can somebody explain why int problem B it adds mn[i] — i to the answer each time? What does it represent? If mn[i] stores the index of the closest non-friend lying on the right of i, then to me mn[i] — i is just the distance between the person i and it's closest non-friend to the right. Ho can this be related to the number of subarrays? Please help
please help
If mn[i] is the index of closest friend to the right of i, then any valid subarray with its left endpoint at index i can end at {i, i+1,..., mn[i] — 1}. So the number of such subarrays is (mn[i] — i)
Thanks you so much, really. You teach me One very useful thing.
Deleted
I think the solution for C may actually fail. Can't the numbers Ai and Aj have a prime gcd which is greater than root Ai and root Aj like 2*p and 3*p type numbers there we will ignore accounting for p since it is greater than root of them but it will be wrong!!please rectify me if I am wrong..
Deleted
?
Ok I wrote this 272334823 and 272338051 code why they get WA test case 4(19982nd)