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;
}
/*
*/