codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1665.md (22508B)


      1 Source: https://codeforces.com/blog/entry/101663
      2 
      3 Again, I hope that you liked all the problems. Share your ideas and solutions in the comments, because there are always different ones! So, the editorial:
      4 
      5 **A: GCD vs LCM**
      6 
      7 [1665A - GCD vs LCM](/contest/1665/problem/A "Codeforces Round 781 (Div. 2)")
      8 
      9 **Editorial**
     10 
     11 In this problem it is enough to print $n - 3$, $1$, $1$, $1$. It is easy to see that this answer is correct for any $n \ge 4$.
     12 
     13 **Implementation (C++, shishyando)**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 using namespace std;
     18 
     19 int main() {
     20     int T;
     21     cin >> T;
     22     while (T --> 0) {
     23         int n;
     24         cin >> n;
     25         cout << n - 3 << ' ' << 1 << ' ' << 1 << ' ' << 1 << '\n';
     26     }
     27     return 0;
     28 }
     29 ```
     30 
     31 **B: Array Cloning Technique**
     32 
     33 [1665B - Array Cloning Technique](/contest/1665/problem/B "Codeforces Round 781 (Div. 2)")
     34 
     35 **Editorial**
     36 
     37 We will use a greedy technique. Let's find the most common element in the array. Let it be $x$ and let it occur $k$ times in the array. Then let's make a copy where all elements are $x$. To do that we can make a copy of the given array and put all $x$ in one array. Now we will repeat the algorithm for the new array until we get a copy with $n$ numbers $x$.
     38 
     39 **Implementation (C++, shishyando)**
     40 
     41 ```
     42 #include <bits/stdc++.h>
     43 using namespace std;
     44 
     45 int main() {
     46     ios_base::sync_with_stdio(false);
     47     cin.tie(nullptr);
     48     cout.tie(nullptr);
     49     int T;
     50     cin >> T;
     51     while (T --> 0) {
     52         int n;
     53         cin >> n;
     54         map<int, int> q;
     55         for (int i = 0; i < n; ++i) {
     56             int x;
     57             cin >> x;
     58             ++q[x];
     59         }
     60         int am = 0;
     61         for (auto &[x, y] : q) {
     62             am = max(am, y);
     63         }
     64         int ans = 0;
     65         while (am < n) {
     66             int d = min(n - am, am);
     67             ans += 1 + d;
     68             am += d;
     69         }
     70         cout << ans << '\n';
     71     }
     72     return 0;
     73 }
     74 ```
     75 
     76 **C: Tree Infection**
     77 
     78 [1665C - Tree Infection](/contest/1665/problem/C "Codeforces Round 781 (Div. 2)")
     79 
     80 **Editorial**
     81 
     82 Firstly, we can see that for any two different vertices, their children are independent. It means that infection can not spread from children of one vertex to children of another. Also it does not matter how the infection spreads among the children of some vertex, so we only need to know the amount of vertices with the same parent.
     83 
     84 Using this knowledge we can reduce the problem to this one: You are given an array of $k$ positive integers, each integer denotes the amount of healthy vertices with the same parent. Each second you can infect an integer in this array (by injection). Also each second all infected integers decrease by 1 (because of spreading).
     85 
     86 Let's now use a greedy algorithm. We will sort this array in the decreasing order and infect all integers one by one. These injections are always needed because the integers are independent. After that each second all numbers decrease by 1 and we can choose one number to be decreased once more in the same second. This should be the max number.
     87 
     88 This problem can be solved by simulating the whole process, because the sum of all integers in the beginning is $n$.
     89 
     90 **Implementation (C++, shishyando)**
     91 
     92 ```
     93 #include <bits/stdc++.h>
     94 using namespace std;
     95 
     96 int ans;
     97 
     98 void proc(vector<int>& a) {
     99     if (a.empty()) return;
    100     int n = a.size();
    101     int last = 0;
    102     for (int i = 0; i < n; ++i) {
    103         if (a[i] == a[0]) {
    104             last = i;
    105         } else {
    106             break;
    107         }
    108     }
    109     --a[last];
    110     for (int i = 0; i < n; ++i) --a[i];
    111     ++ans;
    112     while (!a.empty() && a.back() <= 0) {
    113         a.pop_back();
    114     }
    115     proc(a);
    116 }
    117 
    118 int main() {
    119     ios_base::sync_with_stdio(false);
    120     cin.tie(nullptr);
    121     cout.tie(nullptr);
    122     int T;
    123     cin >> T;
    124     while (T --> 0) {
    125         int n;
    126         cin >> n;
    127         vector<int> a(n);
    128         ans = 0;
    129         for (int i = 1; i < n; ++i) {
    130             int x;
    131             cin >> x;
    132             ++a[--x];
    133         }
    134         a.emplace_back(1);
    135         sort(a.rbegin(), a.rend());
    136         while (!a.empty() && a.back() <= 0) a.pop_back();
    137         n = a.size();
    138         for (int i = 0; i < n; ++i) {
    139             a[i] = a[i] - (n - i);
    140             ++ans;
    141         }
    142         sort(a.rbegin(), a.rend());
    143         while (!a.empty() && a.back() <= 0) a.pop_back();
    144         proc(a);
    145         cout << ans << '\n';
    146     }
    147     return 0;
    148 }
    149 ```
    150 
    151 **D: GCD Guess**
    152 
    153 [1665D - GCD Guess](/contest/1665/problem/D "Codeforces Round 781 (Div. 2)")
    154 
    155 **Editorial**
    156 
    157 **Solution 1**
    158 
    159 Let's iteratively find the remainder of $x \bmod$ each power of $2$. Initially, we know that $x \bmod 2^0 = x \bmod 1 = 0$. If we know that $x \bmod 2^k = r$, then how do we find $x \bmod 2^{k + 1}$? To do that let's ask $\gcd(x + 2^k - r, 2^{k + 1}) = \gcd(x + 2^k - r, x + 2^k - r + 2^{k + 1})$. If $\gcd = 2^{k + 1}$, then $x \bmod 2^{k + 1} = r + 2^{k - 1}$ else $x \bmod 2^{k + 1} = r$. Using this algorithm we will find $x \bmod 2^{30}$ which is just $x$. It takes exactly $30$ queries.
    160 
    161 **Solution 2**
    162 
    163 Let's consider a set of pairwise coprime numbers ${23, 19, 17, 13, 11, 9, 7, 5, 4}$. Their $\text{lcm} \gt 10^9$ that's why $x \bmod \text{lcm} = x$. Let's find $x \bmod$ each of these numbers. To do that, for each $1 \le i \le 23$ we can ask $\gcd(x + i, x + \text{lcm} + i)$ (the query is $(i, \text{lcm} + i)$). If the $\gcd$ is a multiple of some number from our set then $x \bmod$ this number is $-i$. After that we can use the [chinese remainder theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) to find $x$ that gives the same remainders for numbers from the set. This solution asks only $23$ queries.
    164 
    165 *Observation 1*: It's enough to make only $22$ queries, because if we did not find anything for $1 \le i \le 22$ then we can guarantee that $i = 23$ will do.
    166 
    167 *Observation 2*: All moduli are small, that's why it is possible to use a simplified CRT (check the implementation).
    168 
    169 **Implementation (C++, Artyom123)**
    170 
    171 ```
    172 #include<bits/stdc++.h>
    173 
    174 using namespace std;
    175 
    176 int ask(int a, int b) {
    177     cout << '?' << " " << a << " " << a + b << endl;
    178     int ans;
    179     cin >> ans;
    180     return ans;
    181 }
    182 
    183 void solve() {
    184     int r = 0;
    185     for (int i = 1; i <= 30; i++) {
    186         int ans = ask((1 << (i - 1)) - r, (1 << i));
    187         if (ans == (1 << i)) r += (1 << (i - 1));
    188     }
    189     cout << '!' << " " << r << endl;
    190 }
    191 
    192 int main() {
    193     int t;
    194     cin >> t;
    195     while (t--) solve();
    196     return 0;
    197 }
    198 ```
    199 
    200 **Implementation with CRT (C++, TheScrasse)**
    201 
    202 ```
    203 #include <bits/stdc++.h>
    204 using namespace std;
    205  
    206 #define nl "\n"
    207 #define nf endl
    208 #define ll long long
    209 #define pb push_back
    210 #define _ << ' ' <<
    211  
    212 #define INF (ll)1e18
    213 #define mod 998244353
    214 #define maxn 110
    215 #define lc 1338557220
    216  
    217 ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
    218 ll x, rs[maxn], p;
    219 vector<ll> pw = {23, 19, 17, 13, 11, 9, 7, 5, 4};
    220  
    221 ll ask(ll a, ll b) {
    222     cout << "?" _ a _ b << nf;
    223     ll x; cin >> x; return x;
    224 }
    225  
    226 void clm(ll x) {
    227     cout << "!" _ x << nf;
    228 }
    229  
    230 int main() {
    231     ios::sync_with_stdio(0);
    232     cin.tie(0);
    233  
    234     /* #if !ONLINE_JUDGE && !EVAL
    235         ifstream cin("input.txt");
    236         ofstream cout("output.txt");
    237     #endif */
    238  
    239     // kudos for automatic wa
    240  
    241     cin >> t;
    242     while (t--) {
    243         for (i = 1; i <= 23; i++) {
    244             k = ask(x + i, lc + i);
    245             for (j = 0; j < 9; j++) {
    246                 if (k % pw[j] == 0) rs[j] = i % pw[j];
    247             }
    248         }
    249  
    250         k = 1; p = 1;
    251         for (j = 0; j < 9; j++) {
    252             // cout << "p =" _ p << nf;
    253             while (p % pw[j] != rs[j]) p += k;
    254             k *= pw[j];
    255         }
    256  
    257         clm(lc - p);
    258     }
    259  
    260     return 0;
    261 }
    262 ```
    263 
    264 **E: MinimizOR**
    265 
    266 [1665E - MinimizOR](/contest/1665/problem/E "Codeforces Round 781 (Div. 2)")
    267 
    268 **Editorial**
    269 
    270 The key idea for the solution is that the answer always lies among no more than 31 minimal numbers. According to this idea, it is possible to build a segment tree for minimum on a segment. After that we only need to find no more than 31 minimums on the segment (each time we find one we change it to $\infty$) and, finally, we can find all $OR$s pairwise among these 31 numbers.
    271 
    272 It is also possible to use the Merge Sort Tree and the same idea.
    273 
    274 Now let's prove the key idea: let's prove by induction that if all numbers are less than $2^k$ then it's enough to consider $k + 1$ minimal numbers.
    275 
    276 **Base case**: $k=1$, all numbers are from $0$ to $1$ and the proof is obvious.
    277 
    278 **Inductive step**:
    279 
    280 Let's show that for any $k \ge 1$ if for $k$ the statement is true then it's true for $k + 1$.
    281 
    282 If all numbers have 1 in $k$-th bit then the $k$-th bit of the answer is also 1, that's why we only have to minimize the remaining bits. For these bits we can apply the induction hypothesis that $k + 1$ minimal numbers are enough. If at least two numbers have 0 in their $k$-th bit then the $k$-th bit in the answer is also 0. That's why we only consider only numbers with 0 in $k$-th bit and we have to minimize the remaining bits. Again applying the induction hypothesis, $k + 1$ minimal numbers are enough. If there is exactly one number with 0 in $k$-th bit then the $k$-th bit in the answer is 1 and we have to find $k + 1$ minimal numbers over $k$ bits. They are among $k + 2$ minimal numbers over $k + 1$ bits, so $k + 2$ minimal numbers are enough.
    283 
    284 **Implementation (C++, Artyom123)**
    285 
    286 ```
    287 #include<bits/stdc++.h>
    288 
    289 using namespace std;
    290 
    291 const int MAXK = 31;
    292 const int INF = (1 << 30);
    293 
    294 vector<pair<int, int>> t;
    295 
    296 pair<int, int> get(int v, int vl, int vr, int l, int r) {
    297     if (vl >= l && vr <= r) return t[v];
    298     if (r <= vl || l >= vr) return make_pair(INF, INF);
    299     int vm = (vl + vr) / 2;
    300     return min(get(2 * v + 1, vl, vm, l, r), get(2 * v + 2, vm, vr, l, r));
    301 }
    302 
    303 void mod(int v, int vl, int vr, int id, int val) {
    304     if (vr - vl == 1) {
    305         t[v] = make_pair(val, id);
    306         return;
    307     }
    308     int vm = (vl + vr) / 2;
    309     if (id < vm) mod(2 * v + 1, vl, vm, id, val);
    310     else mod(2 * v + 2, vm, vr, id, val);
    311     t[v] = min(t[2 * v + 1], t[2 * v + 2]);
    312 }
    313 
    314 void solve() {
    315     int n;
    316     cin >> n;
    317     vector<int> a(n);
    318     for (auto &c : a) cin >> c;
    319     t.resize(4 * n);
    320     for (int i = 0; i < n; i++) mod(0, 0, n, i, a[i]);
    321     int q;
    322     cin >> q;
    323     while (q--) {
    324         int l, r;
    325         cin >> l >> r;
    326         l--;
    327         vector<pair<int, int>> b;
    328         for (int i = 0; i < min(r - l, MAXK); i++) {
    329             auto now = get(0, 0, n, l, r);
    330             b.push_back(now);
    331             mod(0, 0, n, now.second, INF);
    332         }
    333         int ans = (1LL << 31) - 1;
    334         for (int i = 0; i < (int)b.size(); i++) {
    335             for (int j = i + 1; j < (int)b.size(); j++) ans = min(ans, b[i].first | b[j].first);
    336         }
    337         for (auto &c : b) mod(0, 0, n, c.second, c.first);
    338         cout << ans << "\n";
    339     }
    340 }
    341 
    342 int main() {
    343     ios_base::sync_with_stdio(0);
    344     cin.tie(0);
    345     cout.tie(0);
    346     int t;
    347     cin >> t;
    348     while (t--) solve();
    349     return 0;
    350 }
    351 ```
    352 
    353 **Other solutions (?)**
    354 
    355 **MO's algorithm + van Emde Boas tree :) (C++, wery0)**
    356 
    357 ```
    358 #pragma GCC optimize("Ofast")
    359 // #pragma GCC target("avx,avx2,fma")
    360  
    361 #include <bits/stdc++.h>
    362  
    363 #define F first
    364 #define S second
    365 #define vec vector
    366 #define pb push_back
    367 #define cld complex<ld>
    368 #define pll pair<ll, ll>
    369 #define pdd pair<ld, ld>
    370 #define umap unordered_map
    371 #define uset unordered_set
    372 #define pii pair<int, int>
    373 #define pnn pair<Node*, Node*>
    374 #define all(m) m.begin(), m.end()
    375 #define uid uniform_int_distribution
    376 #define fast cin.tie(0); cout.tie(0); cin.sync_with_stdio(0); cout.sync_with_stdio(0);
    377 using namespace std;
    378 using str = string;
    379 using ll = long long;
    380 using ld = long double;
    381 using uint = unsigned int;
    382 using ull = unsigned long long;
    383 mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    384 template<typename T> bool chmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}
    385 template<typename T> bool chmax(T& a, const T& b) {return b > a ? a = b, 1 : 0;}
    386  
    387 const uint NO = 1<<30;
    388 template<unsigned K>
    389 struct VebTree{
    390     uint mn, mx;
    391     VebTree<(K>>1)> *m[1<<((K+1)>>1)];
    392     VebTree<((K+1)>>1)> *aux;
    393  
    394     VebTree(){
    395         memset(m, 0, sizeof(m));
    396         aux = 0;
    397         mn = mx = NO;
    398     }
    399  
    400     inline bool empty() const{
    401         return mx==NO;
    402     }
    403  
    404     inline uint high(uint x) const{
    405         return x>>(K>>1);
    406     }
    407  
    408     inline uint low(uint x) const{
    409         return x&((1<<(K>>1))-1);
    410     }
    411  
    412     inline uint merge(uint x, uint y) const{
    413         return (x<<(K>>1))+y;
    414     }
    415  
    416     bool find(uint x){
    417         if(x==mn || x==mx) return 1;
    418         return m[high(x)] && m[high(x)]->find(low(x));
    419     }
    420  
    421     void insert(uint x){
    422         if(mx==NO) mn = mx = x;
    423         else if(mn==mx) mn = min(mn, x), mx = max(mx, x);
    424         else if(x<mn || x>mx){
    425             uint add = x<mn ? mn : mx;
    426             mn = min(mn, x);
    427             mx = max(mx, x);
    428             insert(add);
    429         }
    430         else if(K>1){
    431             uint hi = high(x), lo = low(x);
    432             if(!m[hi]) m[hi] = new VebTree<(K>>1)>();
    433             if(m[hi]->empty()){
    434                 if(!aux) aux = new VebTree<((K+1)>>1)>();
    435                 aux->insert(hi);
    436             }
    437             m[hi]->insert(lo);
    438         }
    439     }
    440  
    441     void rem(uint x){
    442         if(mn==mx){
    443             mn = mx = NO;
    444             return;
    445         }
    446         if(x==mn){
    447             if(!aux || aux->empty()) {mn=mx; return;}
    448             else mn = x = merge(aux->mn, m[aux->mn]->mn);
    449         }
    450         else if(x==mx){
    451             if(!aux || aux->empty()) {mx = mn; return;}
    452             else mx = x = merge(aux->mx, m[aux->mx]->mx);
    453         }
    454         uint hi = high(x), lo = low(x);
    455         m[hi]->rem(lo);
    456         if(m[hi]->empty()) aux->rem(hi);
    457     }
    458  
    459     uint next(uint x){
    460         if(empty() || x>=mx) return NO;
    461         if(x<mn) return mn;
    462         if(K==1) return mx;
    463         uint hi = high(x), lo = low(x);
    464         if(m[hi] && !m[hi]->empty() && m[hi]->mx > lo) return merge(hi, m[hi]->next(lo));
    465         uint next_hi = aux ? aux->next(hi) : NO;
    466         return next_hi==NO ? mx : merge(next_hi, m[next_hi]->mn);
    467     }
    468  
    469     uint prev(uint x){
    470         if(empty() || x<=mn) return NO;
    471         if(x>mx) return mx;
    472         if(K==1) return mn;
    473         uint hi = high(x), lo = low(x);
    474         if(m[hi] && !m[hi]->empty() && m[hi]->mn < lo) return merge(hi, m[hi]->prev(lo));
    475         uint prev_hi = aux ? aux->prev(hi) : NO;
    476         return prev_hi==NO ? mn : merge(prev_hi, m[prev_hi]->mx);
    477     }
    478 };
    479  
    480 const int G = 1e5 + 5, SZB = 300;
    481 int a, z;
    482 int m[G], ans[G];
    483 int cng[G], cnt[G];
    484 array<int, 3> que[G];
    485 int cl, cr;
    486 VebTree<32> veb, lox;
    487  
    488 void add(int ps) {
    489     int res = ++cnt[cng[ps]];
    490     if(res==1){
    491         veb.insert(m[ps]);
    492     }
    493     if(res==2){
    494         lox.insert(m[ps]);
    495     }
    496 }
    497  
    498 void rem(int ps) {
    499     int res = --cnt[cng[ps]];
    500     if(res==0){
    501         veb.rem(m[ps]);
    502     }
    503     if(res==1){
    504         lox.rem(m[ps]);
    505     }
    506 }
    507  
    508 uint go() {
    509     uint o = 0;
    510     uint mn = NO;
    511     vec<int> del;
    512     for(int k=29; k>=0; k--){
    513         uint x = o+(1<<k);
    514         uint cur = veb.prev(x), sz = 0;
    515         if(cur!=NO && cur>=o){
    516             ++sz;
    517             cur = veb.prev(cur);
    518             if(cur!=NO && cur>=o){
    519                 ++sz;
    520             }
    521         }
    522         if(sz==0) o += 1<<k;
    523         else if(sz==1){
    524             uint c = veb.prev(x)+(1<<k);
    525             if(veb.find(c)) chmin(mn, c);
    526             else {
    527                 veb.insert(c);
    528                 del.pb(c);
    529             }
    530             o += 1<<k;
    531         }
    532     }
    533     for(uint i : del) veb.rem(i);
    534     return min({mn, o, lox.mn});
    535 }
    536  
    537 void compress(){
    538     vec<int> kek(a);
    539     for(int q=0; q<a; q++) kek[q] = m[q];
    540     sort(all(kek));
    541     kek.erase(unique(all(kek)), kek.end());
    542     for(int q=0; q<a; q++){
    543         cng[q] = lower_bound(all(kek), m[q])-kek.begin();
    544     }
    545 }
    546  
    547 void solve() {
    548     cin >> a;
    549     for (int q = 0; q < a; q++) cin >> m[q];
    550     cin >> z;
    551     for (int q = 0; q < z; q++) {
    552         int l, r; cin >> l >> r; l--; r--;
    553         que[q] = {l, r, q};
    554     }
    555     sort(que, que + z, [](array<int, 3> & p1, array<int, 3> & p2) {
    556         int l1 = p1[0] / SZB;
    557         int l2 = p2[0] / SZB;
    558         if (l1 != l2) return l1 < l2;
    559         return l1 % 2 == 0 ? p1[1] < p2[1] : p1[1] > p2[1];
    560     });
    561     cl = cr = 0;
    562     compress();
    563     fill(cnt, cnt+a, 0);
    564     add(0);
    565     for (int i = 0; i < z; i++) {
    566         int ql = que[i][0];
    567         int qr = que[i][1];
    568         for (; cr + 1 <= qr; ) add(++cr);
    569         for (; cl - 1 >= ql; ) add(--cl);
    570         for (; cr > qr;) rem(cr--);
    571         for (; cl < ql; ) rem(cl++);
    572         ans[que[i][2]] = go();
    573     }
    574     for(; cl<=cr;) rem(cr--);
    575     for (int q = 0; q < z; q++) cout << ans[q] << "\n";
    576 }
    577  
    578 int main() {
    579     fast;
    580     int z; cin >> z;
    581     for (; z--;) {
    582         solve();
    583     }
    584 }
    585 ```
    586 
    587 **DATA STRUCTURES!!! (C++, AlperenT)**
    588 
    589 ```
    590 #include <bits/stdc++.h>
    591 
    592 using namespace std;
    593 
    594 const size_t MEMSIZE = 1e9 / 3.8;  // in bytes
    595  
    596 constexpr size_t MX_ALIGN = alignof(std::max_align_t);
    597 char __attribute__((aligned(MX_ALIGN))) memory[MEMSIZE];
    598 size_t memorypos;
    599 void * operator new(size_t n){
    600   if (memorypos + n >= MEMSIZE) {
    601     memorypos = MEMSIZE / 3;
    602   }
    603   char *ret = memory + memorypos;
    604   memorypos = size_t((memorypos+n+MX_ALIGN-1)&-MX_ALIGN);
    605   return (void*)ret;
    606 }
    607 void operator delete(void *){}
    608 void operator delete(void *, size_t){}
    609 
    610 struct Node{
    611     int l, r, cnt, val;
    612 
    613     Node *lptr = nullptr, *rptr = nullptr;
    614 
    615     Node(int l, int r, int cnt = 0, int val = -1) : l(l), r(r), cnt(cnt), val(val){}
    616 
    617     Node(Node* lptr, Node* rptr) : lptr(lptr), rptr(rptr) {
    618         l = lptr->l, r = rptr->r;
    619 
    620         cnt = lptr->cnt + rptr->cnt;
    621 
    622         val = max(lptr->val, rptr->val);
    623     }
    624 
    625     void extend(){
    626         if(!lptr && l != r){
    627             int m = l + (r - l) / 2;
    628 
    629             lptr = new Node(l, m);
    630             rptr = new Node(m + 1, r);
    631         }
    632     }
    633 
    634     pair<int, int> merge(pair<int, int> a, pair<int, int> b){
    635         return {a.first + b.first, max(a.second, b.second)};
    636     }
    637 
    638     pair<int, int> query(int lq, int rq){
    639         if(lq > rq) return {0, -1};
    640 
    641         extend();
    642 
    643         if(lq == l && rq == r) return {cnt, val};
    644         else{
    645             int m = l + (r - l) / 2;
    646 
    647             pair<int, int> a = lptr->query(lq, min(m, rq)), b = rptr->query(max(m + 1, lq), rq);
    648 
    649             return merge(a, b);
    650         }
    651     }
    652 };
    653 
    654 Node* update(Node* v, int k, int indx){
    655     v->extend();
    656 
    657     if(v->l == v->r) return new Node(v->l, v->r, v->cnt + 1, indx);
    658     else{
    659         if(k <= v->lptr->r) return new Node(update(v->lptr, k, indx), v->rptr);
    660         else return new Node(v->lptr, update(v->rptr, k, indx));
    661     }
    662 }
    663 
    664 const int N = 1e5 + 5;
    665 
    666 int t, n, q, arr[N], l, r, curnum;
    667 
    668 Node* roots[N];
    669 
    670 vector<int> vec;
    671 
    672 pair<int, int> query(int l, int r, int lnum, int rnum){
    673     pair<int, int> p;
    674 
    675     p.first = roots[r]->query(lnum, rnum).first - roots[l - 1]->query(lnum, rnum).first;
    676     p.second = (p.first ? roots[r]->query(lnum, rnum).second : -1);
    677 
    678     for(auto i : vec) if(i >= lnum && i <= rnum) p.first++;
    679     
    680     return p;
    681 }
    682 
    683 void solve(){
    684     cin >> n;
    685 
    686     for(int i = 1; i <= n; i++) cin >> arr[i];
    687 
    688     roots[0] = new Node(0, 1 << 30);
    689 
    690     for(int i = 1; i <= n; i++) roots[i] = update(roots[i - 1], arr[i], i);
    691 
    692     cin >> q;
    693 
    694     while(q--){
    695         cin >> l >> r;
    696 
    697         curnum = 0;
    698 
    699         vec.clear();
    700 
    701         for(int i = 29; i >= 0; i--){
    702             pair<int, int> p = query(l, r, curnum, curnum + (1 << i) - 1);
    703 
    704             if(p.first >= 2) continue;
    705             else if(p.first >= 1 && p.second != -1){
    706                 vec.push_back(arr[p.second] | (1 << i));
    707                 curnum += 1 << i;
    708             }
    709             else{
    710                 curnum += 1 << i;
    711                 for(auto &j : vec) j |= (1 << i);
    712             }
    713         }
    714 
    715         cout << curnum << "\n";
    716     }
    717 }
    718 
    719 int main(){
    720     ios_base::sync_with_stdio(false);cin.tie(NULL);
    721         
    722     cin >> t;
    723 
    724     while(t--){
    725         solve();
    726     }
    727 }
    728 ```
    729 
    730 **No data structures... (C++, vsinitsynav)**
    731 
    732 ```
    733 #include <bits/stdc++.h>
    734  
    735 #define F first
    736 #define S second
    737 #define all(a) a.begin(), a.end()
    738  
    739 using namespace std;
    740 using ll = long long;
    741  
    742 template<class T> bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }
    743 template<class T> bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }
    744  
    745 void solve() {
    746     int n; cin >> n;
    747     vector<int> a(n); for (auto &x : a) cin >> x;
    748     vector<unordered_map<int, vector<int>>> cnt(30);
    749     for (int i = 0; i < n; ++i) {
    750         for (int j = 0; j < 30; ++j) {
    751             cnt[29-j][a[i]>>j].push_back(i);
    752         }
    753     }
    754     int q; cin >> q;
    755     while (q--) {
    756         int l, r; cin >> l >> r; l--; r--;
    757         int x = 0, pref = 0;
    758         vector<int> tmp;
    759         for (int j = 0; j < 30; ++j) {
    760             pref*=2;
    761             vector<int> newtmp;
    762             int k = upper_bound(all(cnt[j][pref]), r) - lower_bound(all(cnt[j][pref]), l);
    763             int k0 = k;
    764             for (auto y : tmp) {
    765                 if (((y>>(29-j))&1) == 0) k++, newtmp.push_back(y);
    766             }
    767             if (k0 == 1) {
    768                 int id = lower_bound(all(cnt[j][pref]), l) - cnt[j][pref].begin();
    769                 tmp.push_back(a[cnt[j][pref][id]]);
    770             }
    771             if (k < 2) pref++;
    772             else tmp.swap(newtmp);
    773         }
    774         cout << pref << "\n";
    775     }
    776 }
    777  
    778 int main() {
    779     ios::sync_with_stdio(0); cin.tie(0);
    780     int t; cin >> t;
    781     while (t--) solve();
    782     return 228/1337;
    783 }
    784 ```
    785 
    786 **Who did what?**
    787 
    788 * Problem A
    789   + Idea: [shishyando](/profile/shishyando "Expert shishyando")
    790   + Polygon: [shishyando](/profile/shishyando "Expert shishyando")
    791 * Problem B
    792   + Idea: [shishyando](/profile/shishyando "Expert shishyando")
    793   + Polygon: [shishyando](/profile/shishyando "Expert shishyando")
    794 * Problem C
    795   + Idea: [shishyando](/profile/shishyando "Expert shishyando")
    796   + Polygon: [shishyando](/profile/shishyando "Expert shishyando")
    797 * Problem D
    798   + Idea: [Artyom123](/profile/Artyom123 "Grandmaster Artyom123")
    799   + Polygon: [shishyando](/profile/shishyando "Expert shishyando")
    800 * Problem E
    801   + Idea: [Kirill22](/profile/Kirill22 "International Grandmaster Kirill22")
    802   + Polygon: [shishyando](/profile/shishyando "Expert shishyando")
    803 * English translation: [shishyando](/profile/shishyando "Expert shishyando")
    804 * Special thanks: [KAN](/profile/KAN "Legendary Grandmaster KAN") for coordinating the coordinator and double checking everything
    805 * Another special thanks: [NEAR](https://near.org/) for supporting the Codeforces Community!
    806 * Yet another special thanks: everyone who participated and tested!