codeforces-scrape

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

1847.md (17425B)


      1 Source: https://codeforces.com/blog/entry/117928
      2 
      3 [1847:A — The Man who became a God](https://codeforces.com/contest/1847/problem/A)
      4 
      5 * Author — [PoPularPlusPlus](/profile/PoPularPlusPlus "Мастер PoPularPlusPlus")
      6 
      7 **tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 using namespace std;
     16 #define ll long long
     17 #define ull unsigned long long 
     18 #define pb(e) push_back(e)
     19 #define sv(a) sort(a.begin(),a.end())
     20 #define sa(a,n) sort(a,a+n)
     21 #define mp(a,b) make_pair(a,b)
     22 #define all(x) x.begin(),x.end()
     23 
     24 void solve(){
     25 	int n , k;
     26 	cin >> n >> k;
     27 	ll arr[n];
     28 	for(int i = 0; i < n; i++)cin >> arr[i];
     29 	vector<ll> v;
     30 	ll sum = 0;
     31 	for(int i = 1; i < n; i++){
     32 		v.pb(abs(arr[i] - arr[i-1]));
     33 		sum += v.back();
     34 	}
     35 	sort(all(v));
     36 	for(int groups = 1; groups < k; groups++){
     37 		sum -= v.back();
     38 		v.pop_back();
     39 	}
     40 	cout << sum << '\n';
     41 }
     42 
     43 int main(){
     44 ios_base::sync_with_stdio(false);
     45 cin.tie(NULL);
     46 	int t;cin >> t;while(t--)
     47 	solve();
     48 	return 0;
     49 }
     50 ```
     51 
     52 [1847:B — Hamon Odyssey](https://codeforces.com/contest/1847/problem/B)
     53 
     54 * Author — [PoPularPlusPlus](/profile/PoPularPlusPlus "Мастер PoPularPlusPlus")
     55 
     56 **tutorial**
     57 
     58 Tutorial is loading...
     59 
     60 **solution**
     61 
     62 ```
     63 #include <iostream>
     64 #include <vector>
     65 using namespace std;
     66 #define ll long long
     67 #define ull unsigned long long 
     68 #define pb(e) push_back(e)
     69 #define sv(a) sort(a.begin(),a.end())
     70 #define sa(a,n) sort(a,a+n)
     71 #define mp(a,b) make_pair(a,b)
     72 #define all(x) x.begin(),x.end()
     73 
     74 void solve(){
     75 	int n;
     76 	cin >> n;
     77 	int arr[n];
     78 	for(int i = 0; i < n; i++)cin >> arr[i];
     79 	int cur = arr[0];
     80 	int part = 1;
     81 	for(int i = 0; i < n; i++){
     82 		cur &= arr[i];
     83 		if(cur == 0){
     84 			if(i == n-1)break;
     85 			part++;
     86 			cur = arr[i + 1];
     87 		}
     88 	}
     89 	if(cur != 0)part--;
     90 	part = max(part,1);
     91 	cout << part << '\n';
     92 }
     93 
     94 int main(){
     95 ios_base::sync_with_stdio(false);
     96 cin.tie(NULL);
     97 	int t;cin >> t;while(t--)
     98 	solve();
     99 	return 0;
    100 }
    101 ```
    102 
    103 [1847:C-Vampiric Powers, anyone?](https://codeforces.com/contest/1847/problem/C)
    104 
    105 * Author — [PoPularPlusPlus](/profile/PoPularPlusPlus "Мастер PoPularPlusPlus")
    106 
    107 **tutorial**
    108 
    109 ### [1847C — Vampiric Powers, anyone?](https://codeforces.com/contest/1847/problem/C)
    110 
    111 At the end of the array, you can only achieve xor of any subarray of the original array.
    112 
    113 **proof**
    114 
    115 Lets denote $f(u,v) =$ xor of all $a_i$ such that $min(u,v) \leq i \lt max(u,v)$. In the first operation you add $f(n,i)$. I.e. $[u_1,v_1)=[n,i)$. It can be proven that $f(u_k,v_k) = f(v_{k-1},v_k)$ in the $k$-th operation which is a range.
    116 
    117 **proof**
    118 
    119 Suppose we have taken $k$ ranges that already satisfy this property. Now, I add a new $k+1$-th range. So, first I need to take the $k$-th range $f(u_k,v_k)$. Now I'm xoring it with the range $f(u_{k - 1}, v_{k - 1})$. As [ $u_k, v_k$) and [ $u_{k - 1}, v_{k - 1}$) share an endpoint, the result for these ranges will be a range.
    120 
    121 **proof**
    122 
    123 For two ranges $f(x,y)$ and $f(y,z)$, if the two ranges do not intersect, the result will be the sum of the two ranges $f(x,z)$. If the two ranges intersect, then the intersections will be cancelled out, and the result will be the difference $f(x,z)$.
    124 
    125 Now, we maintain a boolean array $b$ where $b_i$ is $1$ if there is some $j$ such that $a_1 \oplus a_2 \oplus \cdots \oplus a_j = i$. Initially, $b$ is all $0$. We loop $j$ from $1$ to $n$ and check for each $k$ if $b_k=1$. If it is, then there is some position $p \lt j$ such that $a_1 \oplus a_2 \oplus \cdots \oplus a_p = k$. If we take xor of range from $(p,j]$, then it will be $k \oplus a_1 \oplus a_2 \oplus \cdots \oplus a_j$ (as $a_1 \oplus a_2 \oplus \cdots \oplus a_p$ gets cancelled). This $a_1 \oplus a_2 \oplus \cdots \oplus a_j$ can be stored as we loop ahead. We are looping all possible prefix xors and not all prefix positions because $n$ is large.
    126 
    127 Time Complexity — $O(n \cdot 2^8)$.
    128 
    129 **solution**
    130 
    131 ```
    132 #include <bits/stdc++.h>
    133 using namespace std;
    134  
    135 int main() {
    136     cin.tie(0)->sync_with_stdio(0);
    137     int ntest;
    138     cin >> ntest;
    139     while (ntest--) {
    140         int n;
    141         cin >> n;
    142         vector<int> a(n);
    143         for (auto &i : a)
    144             cin >> i;
    145  
    146         int const max_value = 1 << 8;
    147         vector<char> has_pref(max_value);
    148         has_pref[0] = true;
    149         int cur_xor = 0;
    150         int ans = 0;
    151         for (auto i : a) {
    152             cur_xor ^= i;
    153             for (int pref = 0; pref < max_value; ++pref) {
    154                 if (has_pref[pref]) {
    155                     ans = max(ans, pref ^ cur_xor);
    156                 }
    157             }
    158             has_pref[cur_xor] = true;
    159         }
    160  
    161         cout << ans << '\n';
    162     }
    163 }
    164 ```
    165 
    166 [1847:D Professor Higashikata](https://codeforces.com/contest/1847/problem/D)
    167 
    168 * Author — [PoPularPlusPlus](/profile/PoPularPlusPlus "Мастер PoPularPlusPlus")
    169 
    170 **tutorial**
    171 
    172 Tutorial is loading...
    173 
    174 **solution**
    175 
    176 ```
    177 #include <bits/stdc++.h>
    178 using namespace std;
    179 #define ll long long
    180 #define ull unsigned long long 
    181 #define pb(e) push_back(e)
    182 #define sv(a) sort(a.begin(),a.end())
    183 #define sa(a,n) sort(a,a+n)
    184 #define mp(a,b) make_pair(a,b)
    185 #define vf first
    186 #define vs second
    187 #define all(x) x.begin(),x.end()
    188  
    189 void solve(){
    190 	int n , m , q;
    191 	cin >> n >> m >> q;
    192 	string st;
    193 	cin >> st;
    194 	vector<pair<int,int>> ranges;
    195 	for(int i = 0; i < m; i++){
    196 		int l , r;
    197 		cin >> l >> r;
    198 		l--;
    199 		r--;
    200 		ranges.pb(mp(l,r));
    201 	}
    202 	set<int> s;
    203 	for(int i = 0; i < n; i++)s.insert(i);
    204 	vector<int> v;
    205 	int pos_in_v[n];
    206 	memset(pos_in_v,-1,sizeof pos_in_v);
    207 	for(int i = 0; i < m; i++){
    208 		auto it = s.lower_bound(ranges[i].vf);
    209 		vector<int> toerase;
    210 		while(it != s.end() && (*it) <= ranges[i].vs){
    211 			toerase.pb((*it));
    212 			v.pb(toerase.back());
    213 			pos_in_v[toerase.back()] = v.size()-1;
    214 			it++;
    215 		}
    216 		while(toerase.size()){
    217 			s.erase(toerase.back());
    218 			toerase.pop_back();
    219 		}
    220 	}
    221 	int cnt = 0;
    222 	for(int i = 0; i < n; i++){
    223 		if(st[i] == '1')cnt++;
    224 	}
    225 	int ans = 0;
    226 	for(int i = 0; i < min(cnt , (int)v.size()); i++){
    227 		if(st[v[i]] == '0')ans++;
    228 	}
    229 	
    230 	while(q--){
    231 		int pos;
    232 		cin >> pos;
    233 		pos--;
    234 		if(pos_in_v[pos] != -1 && pos_in_v[pos] < cnt){
    235 			if(st[pos] == '0'){
    236 				ans--;
    237 			}
    238 			else ans++;
    239 		}
    240 		if(st[pos] == '0'){
    241 			st[pos] = '1';
    242 			cnt++;
    243 			if(cnt <= v.size() && st[v[cnt-1]] == '0')ans++;
    244 		}
    245 		else {
    246 			st[pos] = '0';
    247 			if(cnt > 0 && cnt <= v.size() && st[v[cnt-1]] == '0')ans--;
    248 			cnt--;
    249 		}
    250 		cout << ans << '\n';
    251 	}
    252 }
    253  
    254 int main(){
    255 ios_base::sync_with_stdio(false);
    256 cin.tie(NULL);
    257 	//int t;cin >> t;while(t--)
    258 	solve();
    259 	return 0;
    260 }
    261 ```
    262 
    263 [1847:E Triangle Platinum?](https://codeforces.com/contest/1847/problem/E)
    264 
    265 * Author — [StArChAn](/profile/StArChAn "Эксперт StArChAn")
    266 
    267 **tutorial**
    268 
    269 Tutorial is loading...
    270 
    271 **deterministic solution**
    272 
    273 ```
    274 #include<bits/stdc++.h>
    275 using namespace std;
    276 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
    277 int n, ans[5005], holy[10][10][10];
    278 map<vector<int>, int> GG;
    279 int area(int x, int y, int z)
    280 {
    281     int ok = max(x, max(y, z));
    282     int sum = x+y+z;
    283     if(2*ok >= sum) return 0;
    284     return sum*(sum-2*x)*(sum-2*y)*(sum-2*z);
    285 }
    286 int query(vector<int> v)
    287 {
    288     sort(v.begin(), v.end());
    289     if(GG.find(v) != GG.end()) return GG[v];
    290     cout << "? " << v[0] << " " << v[1] << " " << v[2] << endl;
    291     int ret; cin >> ret; assert(ret != -1); return GG[v] = ret;
    292 }
    293 void print(bool found = true)
    294 {
    295     if(!found)
    296     {
    297         cout << "! -1" << endl;
    298         exit(0);
    299     }
    300     cout << "! ";
    301     for(int i = 1; i <= n; i++) cout << ans[i] << " ";
    302     cout << endl; exit(0);
    303 }
    304 bool works()
    305 {
    306     for(int i = 1; i <= n; i++)
    307     {
    308         for(int j = i+1; j <= n; j++)
    309         {
    310             for(int k = j+1; k <= n; k++)
    311             {
    312                 if(area(ans[i], ans[j], ans[k]) != holy[i][j][k])
    313                     return false;
    314             }
    315         }
    316     }
    317     return true;
    318 }
    319 void brute()
    320 {
    321     for(int i = 1; i <= n; i++)
    322     {
    323         for(int j = i+1; j <= n; j++)
    324         {
    325             for(int k = j+1; k <= n; k++)
    326                 holy[i][j][k] = query({i, j, k});
    327         }
    328     }
    329     int mask = 1<<(2*n);
    330     int lol = 0;
    331     int workser = -1;
    332     for(int i = 0; i < mask; i++)
    333     {
    334         int copy = i;
    335         for(int k = 1; k <= n; k++)
    336         {
    337             ans[k] = 1+copy%4;
    338             copy/=4;
    339         }
    340         if(works())
    341         {
    342             workser = i;
    343             lol++;
    344         }
    345     }
    346     assert(lol);
    347     if(lol > 1) print(false);
    348     int copy = workser;
    349     for(int k = 1; k <= n; k++)
    350     {
    351         ans[k] = 1+copy%4;
    352         copy/=4;
    353     }
    354     print();
    355 }
    356 
    357 signed main()
    358 {
    359     ios_base::sync_with_stdio(false); cin >> n;
    360     if(n <= 8) brute();
    361     map<int, int> nice;
    362     for(int i = 1; i <= 4; i++) nice[area(i, i, i)] = i;
    363     int a, b, X;
    364     
    365     {
    366         bool found = false;
    367         for(int i = 1; i <= min(n, 9) && !found; i++)
    368         {
    369             for(int j = i+1; j <= min(n, 9) && !found; j++)
    370             {
    371                 for(int k = j+1; k <= min(n, 9) && !found; k++)
    372                 {
    373                     if(nice[query({i, j, k})])
    374                     {
    375                         a = i;
    376                         b = j;
    377                         X = nice[query({i, j, k})];
    378                         found = true;
    379                     }
    380                 }
    381             }
    382         }
    383     }
    384     if(X > 1)
    385     {
    386         map<int, int> ok;
    387         for(int i = 1; i <= 4; i++) ok[area(i, X, X)] = i;
    388         for(int i = 1; i <= n; i++) ans[i] = ((i==a) || (i==b))? X : ok[query({a, b, i})];
    389         print();
    390         return 0;
    391     }
    392     vector<int> non_ones;
    393     for(int i = 1; i <= n; i++)
    394     {
    395         if(i == a || i == b || query({i, a, b}))
    396             ans[i] = 1;
    397         else
    398             non_ones.push_back(i);
    399         if(non_ones.size() == 4) break;
    400     }
    401     if(non_ones.empty()) print();
    402     map<int, int> ok;
    403     for(int i = 2; i <= 4; i++) ok[area(1, i, i)] = i;
    404     int x, y, Z; x = y = -1; Z = 0;
    405     for(int i = 0; i < non_ones.size() && (Z == 0); i++)
    406     {
    407         for(int j = i+1; j < non_ones.size() && (Z == 0); j++)
    408         {
    409             if(ok[query({a, non_ones[i], non_ones[j]})])
    410             {
    411                 x = non_ones[i];
    412                 y = non_ones[j];
    413                 Z = ok[query({a, non_ones[i], non_ones[j]})];
    414             }
    415         }
    416     }
    417     if(x == -1) print(false);
    418     map<int, int> fin; ans[x] = ans[y] = Z; 
    419     for(int i = 1; i <= 4; i++) fin[area(Z, Z, i)] = i;
    420     for(int i = 1; i <= n; i++) ans[i] = ans[i]? ans[i] : fin[query({x, y, i})];
    421     print();
    422     return 0;
    423 }
    424 ```
    425 
    426 **randomisation solution**
    427 
    428 ```
    429 #include <bits/stdc++.h>
    430 using namespace std;
    431 #define int long long
    432 #define INF (int)1e18
    433 #define f first
    434 #define s second
    435  
    436 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
    437 const int N = 5005;
    438 int ans[N];
    439 int n;
    440 int dp[5][5][5];
    441 int holy[11][11][11];
    442  
    443 int area(int a, int b, int c){
    444     if (a >= b + c) return 0;
    445     if (b >= a + c) return 0;
    446     if (c >= a + b) return 0;
    447     
    448     int s = (a + b + c);
    449     return s * (s - 2 * a) * (s - 2 * b) * (s - 2 * c);
    450 }
    451  
    452 int query(int a, int b, int c){
    453     cout << "? " << a << " " << b << " " << c << endl;
    454     int ans; cin >> ans;
    455     return ans;
    456 }
    457  
    458 void print(bool found = true){
    459     if (!found){
    460         cout << "! -1\n";
    461         exit(0);
    462     } else {
    463         cout << "! ";
    464         for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    465         cout << endl;
    466         exit(0);
    467     }
    468 }
    469  
    470 bool works(){
    471     for (int i = 1; i <= n; i++){
    472         for (int j = i + 1; j <= n; j++){
    473             for (int k = j + 1; k <= n; k++){
    474                 if (area(ans[i], ans[j], ans[k]) != holy[i][j][k])
    475                     return false;
    476             }
    477         }
    478     }
    479     
    480     return true;
    481 }
    482  
    483 void brutesmall(){
    484     for (int i = 1; i <= n; i++){
    485         for (int j = i + 1; j <= n; j++){
    486             for (int k = j + 1; k <= n; k++){
    487                 holy[i][j][k] = query(i, j, k);
    488             }
    489         }
    490     }
    491     
    492     int mask = 1 << (2 * n);
    493     int lol = 0;
    494     for (int i = 0; i < mask; i++){
    495         int copy = i;
    496         
    497         for (int i = 1; i <= n; i++){
    498             ans[i] = 1 + copy % 4;
    499             copy /= 4;
    500         }
    501         
    502         if (works()){
    503             lol++;
    504         }
    505     }
    506     
    507     if (lol > 1) print(false);
    508     
    509     for (int i = 0; i < mask; i++){
    510         int copy = i;
    511         
    512         for (int i = 1; i <= n; i++){
    513             ans[i] = 1 + copy % 4;
    514             copy /= 4;
    515         }
    516         
    517         if (works()){
    518             print();
    519         }
    520     }
    521 }
    522  
    523 void Solve() 
    524 {
    525     cin >> n;
    526     
    527     for (int i = 1; i <= 4; i++){
    528         for (int j = 1; j <= 4; j++){
    529             for (int k = 1; k <= 4; k++){
    530                 dp[i][j][k] = area(i, j, k);
    531             }
    532         }
    533     }
    534     
    535     if (n < 9){
    536         brutesmall();
    537     }
    538     
    539     vector <int> tuple(4, -1);
    540     while (true){
    541         if (tuple[0] != -1) break;
    542         int p1 = 1 + RNG() % n;
    543         int p2 = 1 + RNG() % n;
    544         int p3 = 1 + RNG() % n;
    545         
    546         if (p1 == p2 || p2 == p3 || p3 == p1) continue;
    547         int ar = query(p1, p2, p3);
    548         for (int j = 1; j <= 4; j++){
    549             if (ar == dp[j][j][j]){
    550                 tuple[0] = p1;
    551                 tuple[1] = p2;
    552                 tuple[2] = p3;
    553                 tuple[3] = j;
    554             }
    555         }
    556     }
    557     
    558     for (int i = 0; i < 3; i++) ans[tuple[i]] = tuple[3];
    559     
    560     if (tuple[3] == 1){
    561         vector <int> nv;
    562         for (int i = 1; i <= n; i++){
    563             if (ans[i] > 0) continue;
    564             
    565             int fetch = query(tuple[0], tuple[1], i);
    566             if (fetch == 0) {
    567                 nv.push_back(i);
    568                 if (nv.size() > 3) break;
    569             } else {
    570                 ans[i] = 1;
    571             }
    572         }
    573         
    574         if (nv.size() == 0) print();
    575         
    576         vector <int> ntuple(3, -1);
    577         for (int i1 = 0; i1 < nv.size(); i1++){
    578             for (int i2 = i1 + 1; i2 < nv.size(); i2++){
    579                 int ok = query(tuple[0], nv[i1], nv[i2]);
    580                 
    581                 for (int j = 2; j <= 4; j++){
    582                     if (ok == dp[1][j][j]){
    583                         ntuple[0] = nv[i1];
    584                         ntuple[1] = nv[i2];
    585                         ntuple[2] = j;
    586                     }
    587                 }
    588             }
    589         }
    590         
    591         if (ntuple[0] == -1) print(false);
    592         ans[ntuple[0]] = ntuple[2];
    593         ans[ntuple[1]] = ntuple[2];
    594         
    595         tuple[0] = ntuple[0];
    596         tuple[1] = ntuple[1];
    597         tuple[2] = -1;
    598         tuple[3] = ntuple[2];
    599     }
    600     
    601     for (int i = 1; i <= n; i++){
    602         if (ans[i] > 0) continue;
    603         
    604         int fetch = query(tuple[0], tuple[1], i);
    605         for (int j = 1; j <= 4; j++){
    606             if (dp[tuple[3]][tuple[3]][j] == fetch)
    607                 ans[i] = j;
    608         }
    609     }
    610     
    611     print();
    612 }
    613  
    614 int32_t main() 
    615 {
    616     auto begin = std::chrono::high_resolution_clock::now();
    617     ios_base::sync_with_stdio(0);
    618     cin.tie(0);
    619     int t = 1;
    620  //   cin >> t;
    621     for(int i = 1; i <= t; i++) 
    622     {
    623         Solve();
    624     }
    625     return 0;
    626 }
    627 ```
    628 
    629 [1847:F The Boss's Identity](https://codeforces.com/contest/1847/problem/F)
    630 
    631 * Idea — [astoria](/profile/astoria "Кандидат в мастера astoria")
    632 * Prepared by — [PoPularPlusPlus](/profile/PoPularPlusPlus "Мастер PoPularPlusPlus")
    633 
    634 **tutorial**
    635 
    636 Tutorial is loading...
    637 
    638 **solution**
    639 
    640 ```
    641 #include <bits/stdc++.h>
    642 using namespace std;
    643 #define ll long long
    644 #define ull unsigned long long 
    645 #define pb(e) push_back(e)
    646 #define sv(a) sort(a.begin(),a.end())
    647 #define sa(a,n) sort(a,a+n)
    648 #define mp(a,b) make_pair(a,b)
    649 #define vf first
    650 #define vs second
    651 #define all(x) x.begin(),x.end()
    652 
    653 const int B = 31;
    654 
    655 struct item {
    656 	ll pos , bit, idx;
    657 };
    658 
    659 item make(ll pos , ll bit , ll idx){
    660 	item res;
    661 	res.pos = pos;
    662 	res.bit = bit;
    663 	res.idx = idx;
    664 	return res;
    665 }
    666 
    667 void solve(){
    668     int n;
    669 	cin >> n;
    670 	int qu;
    671 	cin >> qu;
    672 	int arr[n];
    673 	for(int i = 0; i < n; i++)cin >> arr[i];
    674 	if(n == 1){
    675 		while(qu--){
    676 			int x;
    677 			cin >> x;
    678 			if(x < arr[0])cout << 1 << '\n';
    679 			else cout << -1 << '\n';
    680 		}
    681 		return;
    682 	}
    683 	vector<pair<ll,ll>> v;
    684 	queue<item> q;
    685 	bool vis[n][B];
    686 	memset(vis,0,sizeof vis);
    687 	for(int i = 0; i < n; i++){
    688 		for(int j = 0; j < B; j++){
    689 			if((arr[i] & (1 << j)) > 0){
    690 				vis[i][j] = 1;
    691 			}
    692 		}
    693 		v.pb(mp(i , arr[i]));
    694 	}
    695 	for(int i = 0; i < n - 1; i++){
    696 		v.pb(mp(n+i,arr[i]|arr[i+1]));
    697 	}
    698 	for(int j = 0; j < B; j++){
    699 		if(vis[n-1][j])q.push(make(n+n-1,j,0));
    700 	}
    701 	for(int i = 0; i < n - 1; i++){
    702 		for(int j = 0; j < B; j++){
    703 			if(vis[i][j])q.push(make(n+n+i,j,(i+1)%(n-1)));
    704 		}
    705 	}
    706 	int val[n-1];
    707 	for(int i = 0; i < n-1; i++)val[i] = arr[i]|arr[i+1];
    708 	while(q.size()){
    709 		item it = q.front();
    710 		q.pop();
    711 		if((val[it.idx] & (1 << it.bit)) > 0){
    712 			continue;
    713 		}
    714 		val[it.idx] += (1 << it.bit);
    715 		if(v.back().vf == it.pos){
    716 			v.pop_back();
    717 		}
    718 		v.pb(mp(it.pos , val[it.idx]));
    719 		q.push(make(it.pos + n , it.bit , (it.idx + 1)%(n-1)));
    720 	}
    721 	
    722 	// first part gets over where v[i].first contains position in ascending order and v[i].second contains the value to what has become on that position.
    723 	
    724 	
    725 	for(int i = 1; i < v.size(); i++){
    726 		v[i].vs = max(v[i].vs , v[i-1].vs);
    727 	}
    728 
    729 	while(qu--){
    730 		int x;
    731 		cin >> x;
    732 		ll l = 0 , r = v.size()-1;
    733 		ll res = -1;
    734 		while(l <= r){
    735 			int mid = (l + r)/2;
    736 			if(v[mid].vs <= x){
    737 				l = mid + 1;
    738 			}
    739 			else {
    740 				r = mid - 1;
    741 				res = v[mid].vf+1;
    742 			}
    743 		}
    744 		cout << res << '\n';
    745 	}
    746 }
    747 
    748 int main(){
    749 ios_base::sync_with_stdio(false);
    750 cin.tie(NULL);
    751 	int t;cin >> t;while(t--)
    752 	solve();
    753 	return 0;
    754 }
    755 ```