codeforces-scrape

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

2152.md (14902B)


      1 Source: https://codeforces.com/blog/entry/146988
      2 
      3 Thank you for your participation!
      4 
      5 Problem A, B were authored by [djm03178](/profile/djm03178 "Master djm03178").
      6 
      7 Problem C was authored by [middle_man](/profile/middle_man "International Grandmaster middle_man").
      8 
      9 Problem D was authored by [qwerasdfzxcl](/profile/qwerasdfzxcl "Grandmaster qwerasdfzxcl").
     10 
     11 Problem E, F, G, H1, H2 were authored by [ko_osaga](/profile/ko_osaga "Legendary Grandmaster ko_osaga").
     12 
     13 [2152A - Increase or Smash](/contest/2152/problem/A)
     14 
     15 **Spoiler**
     16 
     17 Tutorial is loading...
     18 
     19 **Code**
     20 
     21 ```
     22 #include <bits/stdc++.h>
     23 using namespace std;
     24 
     25 int main()
     26 {
     27 	ios::sync_with_stdio(false);
     28 	cin.tie(0);
     29 	
     30 	int t;
     31 	cin >> t;
     32 	while (t--)
     33 	{
     34 		int n;
     35 		cin >> n;
     36 		set<int> s;
     37 		for (int i = 0; i < n; i++)
     38 		{
     39 			int x;
     40 			cin >> x;
     41 			s.insert(x);
     42 		}
     43 		cout << s.size() * 2 - 1 << '\n';
     44 	}
     45 }
     46 ```
     47 
     48 [2152B - Catching the Krug](/contest/2152/problem/B)
     49 
     50 **Spoiler**
     51 
     52 Tutorial is loading...
     53 
     54 **Code**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58 using namespace std;
     59 
     60 int main()
     61 {
     62 	ios::sync_with_stdio(false);
     63 	cin.tie(0);
     64 
     65 	int t;
     66 	cin >> t;
     67 	while (t--)
     68 	{
     69 		int n, ra, ca, rb, cb;
     70 		cin >> n >> ra >> ca >> rb >> cb;
     71 		int ans = 0;
     72 		if (rb > ra)
     73 			ans = max(ans, rb);
     74 		else if (rb < ra)
     75 			ans = max(ans, n - rb);
     76 		if (cb > ca)
     77 			ans = max(ans, cb);
     78 		else if (cb < ca)
     79 			ans = max(ans, n - cb);
     80 		cout << ans << '\n';
     81 	}
     82 }
     83 ```
     84 
     85 [2152C - Triple Removal](/contest/2152/problem/C)
     86 
     87 **Spoiler**
     88 
     89 Tutorial is loading...
     90 
     91 **Code**
     92 
     93 ```
     94 /*
     95 * T1 Thanks Round
     96 * Problem triple-removal
     97 * Main Correct Solution
     98 */
     99 
    100 #include <bits/stdc++.h>
    101 using namespace std;
    102 
    103 const int MAX = 250'010;
    104 
    105 int A[MAX];
    106 
    107 int diff[MAX];
    108 int diffsum[MAX];
    109 
    110 int sum[2][MAX];
    111 
    112 void solve() {
    113 	int N, Q;
    114 	cin >> N >> Q;
    115 	int i;
    116 	for (i = 1; i <= N; i++) cin >> A[i];
    117 	for (i = 1; i <= N; i++) {
    118 		sum[0][i] = sum[0][i - 1];
    119 		sum[1][i] = sum[1][i - 1];
    120 		sum[A[i]][i]++;
    121 
    122 		diff[i] = A[i] != A[i - 1];
    123 		diffsum[i] = diffsum[i - 1] + diff[i];
    124 	}
    125 	int l, r;
    126 	for (i = 1; i <= Q; i++) {
    127 		cin >> l >> r;
    128 
    129 		int z, o;
    130 		z = sum[0][r] - sum[0][l - 1];
    131 		o = sum[1][r] - sum[1][l - 1];
    132 		if (z % 3) {
    133 			cout << -1 << '\n';
    134 			continue;
    135 		}
    136 		if (o % 3) {
    137 			cout << -1 << '\n';
    138 			continue;
    139 		}
    140 
    141 		int sum = z / 3 + o / 3;
    142 		if (diffsum[r] - diffsum[l] == (r - l)) sum++;
    143 		cout << sum << '\n';
    144 	}
    145 }
    146 
    147 signed main() {
    148 	ios::sync_with_stdio(false), cin.tie(0);
    149 	int t, T;
    150 	cin >> T;
    151 	for (t = 1; t <= T; t++) solve();
    152 }
    153 ```
    154 
    155 [2152D - Division Versus Addition](/contest/2152/problem/D)
    156 
    157 **Spoiler**
    158 
    159 Tutorial is loading...
    160 
    161 **Code**
    162 
    163 ```
    164 #include <bits/stdc++.h>
    165 
    166 using namespace std;
    167 using ll = long long;
    168 
    169 constexpr int MAXN = 250000;
    170 
    171 int a[MAXN + 100];
    172 ll prf[MAXN + 100][4];
    173 
    174 void solve(){
    175     int n, q;
    176     scanf("%d %d", &n, &q);
    177 
    178     for (int i=1;i<=n;i++) scanf("%d", a+i);
    179     
    180     for (int i=1;i<=n;i++){
    181         for (int j=0;j<3;j++) prf[i][j] = prf[i-1][j];
    182         
    183         int typ = 2;
    184         if (popcount((unsigned)a[i]) == 1) typ = 0;
    185         else if (popcount((unsigned)a[i]-1) == 1) typ = 1;
    186 
    187         prf[i][typ]++;
    188 
    189         prf[i][3] = prf[i-1][3] + (31 - countl_zero((unsigned)a[i]));
    190     }
    191 
    192     while(q--){
    193         int l, r;
    194         scanf("%d %d", &l, &r);
    195 
    196         ll cnt[3] = {0};
    197         for (int j=0;j<3;j++) cnt[j] = prf[r][j] - prf[l-1][j];
    198 
    199         ll ans = prf[r][3] - prf[l-1][3] + cnt[2] + cnt[1] / 2;
    200         printf("%lld\n", ans);
    201     }
    202 }
    203 
    204 int main(){
    205     int t;
    206     scanf("%d", &t);
    207 
    208     while(t--) solve();
    209 }
    210 ```
    211 
    212 [2152E - Monotone Subsequence](/contest/2152/problem/E)
    213 
    214 **Spoiler**
    215 
    216 Tutorial is loading...
    217 
    218 **Code**
    219 
    220 ```
    221 #include <bits/stdc++.h>
    222 using namespace std;
    223 using lint = long long;
    224 using pi = array<lint, 2>;
    225 #define sz(v) ((int)(v).size())
    226 #define all(v) (v).begin(), (v).end()
    227 #define cr(v, n) (v).clear(), (v).resize(n);
    228 
    229 void solve() {
    230 	int n;
    231 	cin >> n;
    232 	vector<int> ord(n * n + 1);
    233 	iota(all(ord), 0);
    234 	auto query = [&](vector<int> v) {
    235 		cout << "? " << sz(v);
    236 		for (auto &x : v)
    237 			cout << " " << x + 1;
    238 		cout << endl;
    239 		int y;
    240 		cin >> y;
    241 		v.resize(y);
    242 		for (auto &x : v)
    243 			cin >> x, x--;
    244 		return v;
    245 	};
    246 	vector<int> dp(n * n + 1, n);
    247 	for (int i = 0; i < n; i++) {
    248 		auto cur_ord = query(ord);
    249 		if (sz(cur_ord) > n) {
    250 			cout << "!";
    251 			for (int i = 0; i < n+1; i++)
    252 				cout << " " << cur_ord[i] + 1;
    253 			cout << endl;
    254 			return;
    255 		}
    256 		vector<int> new_ord;
    257 		for (auto &x : ord) {
    258 			if (!binary_search(all(cur_ord), x)) {
    259 				new_ord.push_back(x);
    260 			} else dp[x] = i;
    261 		}
    262 		ord = new_ord;
    263 	}
    264 	int cur = n;
    265 	vector<int> ans;
    266 	for (int i = n * n; i >= 0; i--) {
    267 		if (dp[i] == cur) {
    268 			ans.push_back(i);
    269 			cur--;
    270 		}
    271 	}
    272 	if(sz(ans) != n + 1){
    273 	    cerr << cur << endl;
    274 	    for(auto &x : dp) cerr << x << " ";
    275 	    cerr << endl;
    276 	}
    277 	reverse(all(ans));
    278 	assert(sz(ans) == n+1);
    279 	cout << "!";
    280 	for (auto &x : ans)
    281 		cout << " " << x + 1;
    282 	cout << endl;
    283 }
    284 
    285 int main() {
    286 	int tc;
    287 	cin >> tc;
    288 	while (tc--)
    289 		solve();
    290 }
    291 ```
    292 
    293 [2152F - Triple Attack](/contest/2152/problem/F)
    294 
    295 **Spoiler**
    296 
    297 Tutorial is loading...
    298 
    299 **Code**
    300 
    301 ```
    302 #include <bits/stdc++.h>
    303 using namespace std;
    304 using lint = long long;
    305 using pi = array<lint, 2>;
    306 #define sz(v) ((int)(v).size())
    307 #define all(v) (v).begin(), (v).end()
    308 #define cr(v, n) (v).clear(), (v).resize(n);
    309 const int MAXN = 500005;
    310 
    311 int nxt1[20][MAXN], dep1[MAXN];
    312 pi nxt2[20][MAXN];
    313 
    314 int main() {
    315 	ios::sync_with_stdio(false);
    316 	cin.tie(0);
    317 	cout.tie(0);
    318 	
    319 	int T;
    320 	cin >> T;
    321 	
    322 	while (T--){
    323     	int n, t;
    324     	cin >> n >> t;
    325     	t++;
    326     	vector<int> a(n);
    327     	for (int i = 0; i < n; i++)
    328     		cin >> a[i];
    329     	
    330     	// EDIT: added init statements for globals
    331     	for (int i = 0; i < n+5; i++){
    332     	    for (int j = 0; j < 20; j++) nxt1[j][i]=0,nxt2[j][i]={0,0};
    333     	    dep1[i]=0;
    334     	}
    335     		
    336     	int j = 0;
    337     	for (int i = 0; i < n; i++) {
    338     		while (j < n && a[j] < a[i] + t)
    339     			j++;
    340     		nxt1[0][i] = j;
    341     	}
    342     	nxt1[0][n] = n;
    343     	for (int i = n - 1; i >= 0; i--)
    344     		dep1[i] = dep1[nxt1[0][i]] + 1;
    345     	for (int i = 1; i < 20; i++) {
    346     		for (int j = 0; j <= n; j++)
    347     			nxt1[i][j] = nxt1[i - 1][nxt1[i - 1][j]];
    348     	}
    349     	auto lca = [&](int u, int v) {
    350     		if (dep1[u] > dep1[v])
    351     			swap(u, v);
    352     		int dx = dep1[v] - dep1[u];
    353     		for (int i = 0; dx; i++) {
    354     			if (dx & 1) {
    355     				v = nxt1[i][v];
    356     			}
    357     			dx >>= 1;
    358     		}
    359     		if (u == v)
    360     			return u;
    361     		for (int i = 19; i >= 0; i--) {
    362     			if (nxt1[i][u] != nxt1[i][v]) {
    363     				u = nxt1[i][u];
    364     				v = nxt1[i][v];
    365     			}
    366     		}
    367     		return nxt1[0][u];
    368     	};
    369     	for (int i = 0; i < n; i++) {
    370     		int z = lca(i, i + 1);
    371     		nxt2[0][i] = pi{z, dep1[i] + dep1[i + 1] - 2 * dep1[z]};
    372     	}
    373     	nxt2[0][n] = pi{n, 0};
    374     	for (int i = 1; i < 20; i++) {
    375     		for (int j = 0; j <= n; j++) {
    376     			auto [n1, d1] = nxt2[i - 1][j];
    377     			auto [n2, d2] = nxt2[i - 1][n1];
    378     			nxt2[i][j] = pi{n2, d1 + d2};
    379     		}
    380     	}
    381     	auto gp = [&](int l, int r) {
    382     		int ans = 0;
    383     		for (int i = 19; i >= 0; i--) {
    384     			if (nxt1[i][l] < r) {
    385     				l = nxt1[i][l];
    386     				ans += (1 << i);
    387     			}
    388     		}
    389     		return ans + 1;
    390     	};
    391     	int q;
    392     	cin >> q;
    393     	while (q--) {
    394     		int l, r;
    395     		cin >> l >> r;
    396     		l--;
    397     		if (r - l <= 2) {
    398     			cout << r - l << "\n";
    399     			continue;
    400     		}
    401     		int ans = 0;
    402     		for (int i = 19; i >= 0; i--) {
    403     			if (nxt2[i][l][0] < r) {
    404     				ans += nxt2[i][l][1];
    405     				l = nxt2[i][l][0];
    406     			}
    407     		}
    408     		if (l + 1 <= r)
    409     			ans += gp(l, r);
    410     		if (l + 2 <= r)
    411     			ans += gp(l + 1, r);
    412     		cout << ans << "\n";
    413     	}
    414 	}
    415 }
    416 ```
    417 
    418 [2152G - Query Jungle](/contest/2152/problem/G)
    419 
    420 **Spoiler**
    421 
    422 Tutorial is loading...
    423 
    424 **Code**
    425 
    426 ```
    427 #include <bits/stdc++.h>
    428 using namespace std;
    429 using lint = long long;
    430 using pi = array<lint, 2>;
    431 #define sz(a) ((int)(a).size())
    432 #define all(a) (a).begin(), (a).end()
    433 const int MAXN = 250005;
    434 const int MAXT = 1050000;
    435 
    436 struct mtrx {
    437 	int nxt[2];
    438 	mtrx() { nxt[0] = nxt[1] = 0; }
    439 	mtrx(int x) {
    440 		nxt[x] = 1;
    441 		nxt[1 ^ x] = 0;
    442 	}
    443 	mtrx operator+(const mtrx &m) const {
    444 		mtrx ret;
    445 		ret.nxt[0] = nxt[0] + m.nxt[nxt[0] % 2];
    446 		ret.nxt[1] = nxt[1] + m.nxt[(1 + nxt[1]) % 2];
    447 		return ret;
    448 	}
    449 };
    450 
    451 struct node {
    452 	mtrx M[2];
    453 	int lazy;
    454 	node operator+(const node &nd) const {
    455 		node ret;
    456 		ret.M[0] = M[0] + nd.M[0];
    457 		ret.M[1] = M[1] + nd.M[1];
    458 		ret.lazy = 0;
    459 		return ret;
    460 	}
    461 } tree[MAXT];
    462 
    463 void init(int s, int e, int p, vector<pi> &seq) {
    464 	if (s == e) {
    465 		tree[p].M[seq[s][0]] = mtrx(seq[s][1]);
    466 		tree[p].M[1 ^ seq[s][0]] = mtrx();
    467 		return;
    468 	}
    469 	int m = (s + e) / 2;
    470 	init(s, m, 2 * p, seq);
    471 	init(m + 1, e, 2 * p + 1, seq);
    472 	tree[p] = tree[2 * p] + tree[2 * p + 1];
    473 }
    474 
    475 void lazydown(int p) {
    476 	if (tree[p].lazy) {
    477 		for (int i = 2 * p; i < 2 * p + 2; i++) {
    478 			tree[i].lazy ^= 1;
    479 			swap(tree[i].M[0], tree[i].M[1]);
    480 		}
    481 		tree[p].lazy = 0;
    482 	}
    483 }
    484 
    485 void update(int s, int e, int ps, int pe, int p) {
    486 	if (e < ps || pe < s)
    487 		return;
    488 	if (s <= ps && pe <= e) {
    489 		tree[p].lazy ^= 1;
    490 		swap(tree[p].M[0], tree[p].M[1]);
    491 		return;
    492 	}
    493 	int pm = (ps + pe) / 2;
    494 	lazydown(p);
    495 	update(s, e, ps, pm, 2 * p);
    496 	update(s, e, pm + 1, pe, 2 * p + 1);
    497 	tree[p] = tree[2 * p] + tree[2 * p + 1];
    498 }
    499 
    500 int query() { return tree[1].M[1].nxt[0] / 2; }
    501 
    502 vector<int> gph[MAXN];
    503 int a[MAXN], din[MAXN], dout[MAXN];
    504 vector<pi> seq;
    505 
    506 void dfs(int x, int p = -1) {
    507 	din[x] = sz(seq);
    508 	seq.push_back({a[x], 0});
    509 	for (auto &y : gph[x]) {
    510 		if (y != p)
    511 			dfs(y, x);
    512 	}
    513 	seq.push_back({a[x], 1});
    514 	dout[x] = sz(seq);
    515 }
    516 
    517 int main() {
    518 	ios::sync_with_stdio(false);
    519 	cin.tie(0);
    520 	cout.tie(0);
    521 	int T; cin >> T;
    522 	while (T--) {
    523     	int n;
    524     	cin >> n;
    525     	for (int i = 0; i < n; i++)
    526     		cin >> a[i];
    527     		
    528     	for (int i = 0; i < n; i++) gph[i].clear();
    529     	seq.clear();
    530     	
    531     	for (int i = 0; i < n - 1; i++) {
    532     		int u, v;
    533     		cin >> u >> v;
    534     		u--;
    535     		v--;
    536     		gph[u].push_back(v);
    537     		gph[v].push_back(u);
    538     	}
    539     	dfs(0);
    540     	init(0, sz(seq) - 1, 1, seq);
    541     	cout << query() << "\n";
    542     	int q;
    543     	cin >> q;
    544     	while (q--) {
    545     		int v;
    546     		cin >> v;
    547     		v--;
    548     		update(din[v], dout[v] - 1, 0, sz(seq) - 1, 1);
    549     		cout << query() << "\n";
    550     	}
    551 	}
    552 }
    553 ```
    554 
    555 [2152H1 - Victorious Coloring (Easy Version)](/contest/2152/problem/H1)
    556 
    557 **Spoiler**
    558 
    559 Tutorial is loading...
    560 
    561 **Code**
    562 
    563 ```
    564 #include <bits/stdc++.h>
    565 using namespace std;
    566 using lint = long long;
    567 using pi = array<lint, 2>;
    568 #define sz(v) ((int)(v).size())
    569 #define all(v) (v).begin(), (v).end()
    570 #define cr(v, n) (v).clear(), (v).resize(n);
    571 
    572 vector<int> pa;
    573 
    574 int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }
    575 
    576 int main() {
    577 	ios::sync_with_stdio(false);
    578 	cin.tie(0);
    579 	cout.tie(0);
    580 	int T; cin>>T;
    581 	while (T--){
    582 		int n;
    583 		cin >> n;
    584 		vector<array<lint, 3>> edges;
    585 		for (int i = 0; i < n - 1; i++) {
    586 			lint u, v, w;
    587 			cin >> u >> v >> w;
    588 			u--;
    589 			v--;
    590 			edges.push_back({w, u, v});
    591 		}
    592 		sort(all(edges));
    593 		reverse(all(edges));
    594 		cr(pa, 2 * n - 1);
    595 		vector<lint> cost(2 * n - 1);
    596 		vector<pi> ch(2 * n - 1);
    597 		iota(all(pa), 0);
    598 		for (int i = 0; i < n - 1; i++) {
    599 			int u = find(edges[i][1]);
    600 			int v = find(edges[i][2]);
    601 			pa[u] = i + n;
    602 			pa[v] = i + n;
    603 			ch[i + n] = {u, v};
    604 			cost[edges[i][1]] += edges[i][0];
    605 			cost[edges[i][2]] += edges[i][0];
    606 			cost[i + n] -= edges[i][0] * 2;
    607 		}
    608 		for (int i = n; i < 2 * n - 1; i++) {
    609 			cost[i] += cost[ch[i][0]] + cost[ch[i][1]];
    610 		}
    611 		int q;
    612 		cin >> q;
    613 		while (q--) {
    614 			lint x;
    615 			cin >> x;
    616 			vector<lint> dp(2 * n - 1);
    617 			lint dap = 0;
    618 			for (int i = 0; i < 2 * n - 1; i++) {
    619 				if (i >= n) {
    620 					dp[i] += dp[ch[i][0]] + dp[ch[i][1]];
    621 				}
    622 				if (dp[i] + cost[i] < x) {
    623 					dap += x - cost[i] - dp[i];
    624 					dp[i] = x - cost[i];
    625 				}
    626 			}
    627 			cout << dap << "\n";
    628 		}
    629 	}
    630 }
    631 ```
    632 
    633 [2152H2 - Victorious Coloring (Hard Version)](/contest/2152/problem/H2)
    634 
    635 **Spoiler**
    636 
    637 Tutorial is loading...
    638 
    639 **Code**
    640 
    641 ```
    642 #include <bits/stdc++.h>
    643 using namespace std;
    644 using lint = long long;
    645 using pi = array<lint, 2>;
    646 #define sz(v) ((int)(v).size())
    647 #define all(v) (v).begin(), (v).end()
    648 #define cr(v, n) (v).clear(), (v).resize(n);
    649 
    650 vector<int> pa;
    651 
    652 int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }
    653 
    654 int main() {
    655 	ios::sync_with_stdio(false);
    656 	cin.tie(0);
    657 	cout.tie(0);
    658 	int T; cin>>T;
    659 	while (T--){
    660 		int n;
    661 		cin >> n;
    662 		vector<array<lint, 3>> edges;
    663 		for (int i = 0; i < n - 1; i++) {
    664 			lint u, v, w;
    665 			cin >> u >> v >> w;
    666 			u--;
    667 			v--;
    668 			edges.push_back({w, u, v});
    669 		}
    670 		sort(all(edges));
    671 		reverse(all(edges));
    672 		cr(pa, 2 * n - 1);
    673 		vector<lint> cost(2 * n - 1);
    674 		vector<pi> ch(2 * n - 1);
    675 		iota(all(pa), 0);
    676 		for (int i = 0; i < n - 1; i++) {
    677 			int u = find(edges[i][1]);
    678 			int v = find(edges[i][2]);
    679 			pa[u] = i + n;
    680 			pa[v] = i + n;
    681 			ch[i + n] = {u, v};
    682 			cost[edges[i][1]] += edges[i][0];
    683 			cost[edges[i][2]] += edges[i][0];
    684 			cost[i + n] -= edges[i][0] * 2;
    685 		}
    686 		for (int i = n; i < 2 * n - 1; i++) {
    687 			cost[i] += cost[ch[i][0]] + cost[ch[i][1]];
    688 		}
    689 		// (point, slope increase)
    690 		vector<priority_queue<pi, vector<pi>, greater<pi>>> pq(n);
    691 		vector<int> idx(2 * n - 1);
    692 		iota(all(idx), 0);
    693 		for (int i = 0; i < 2 * n - 1; i++) {
    694 			if (i < n) {
    695 				pq[i].push({cost[i], 1});
    696 				continue;
    697 			}
    698 			if (sz(pq[idx[ch[i][0]]]) < sz(pq[idx[ch[i][1]]]))
    699 				swap(ch[i][0], ch[i][1]);
    700 			idx[i] = idx[ch[i][0]];
    701 			while (sz(pq[idx[ch[i][1]]])) {
    702 				auto tp = pq[idx[ch[i][1]]].top();
    703 				pq[idx[ch[i][1]]].pop();
    704 				pq[idx[i]].push(tp);
    705 			}
    706 			if (cost[i] >= pq[idx[i]].top()[0])
    707 				continue;
    708 			if (cost[i] >= lint(2e9))
    709 				continue;
    710 			lint A = 0, B = 0;
    711 			lint pv = -1;
    712 			while (sz(pq[idx[i]])) {
    713 				auto [point, slope] = pq[idx[i]].top();
    714 				pq[idx[i]].pop();
    715 				B += A * (point - pv);
    716 				pv = point;
    717 				A += slope;
    718 				// A x - A * pv + B = x - cost[i]
    719 				// (A - 1) x = A * pv - B - cost[i]
    720 				lint U = A * pv - B - cost[i];
    721 				lint L = A - 1;
    722 				// point <= U / L, so no need to dedup
    723 				if (L > 0) {
    724 					assert(point * L <= U);
    725 					if ((sz(pq[idx[i]]) == 0 || U < pq[idx[i]].top()[0] * L)) {
    726 						lint f1 = U / L - cost[i];
    727 						lint f2 = (U / L + 1 - pv) * A + B;
    728 						// (cost[i], 0) -> (U / L, f1) -> (U / L + 1, f2) -> increase w/ speed A
    729 						pq[idx[i]].push({cost[i], 1});
    730 						pq[idx[i]].push({U / L, f2 - f1 - 1});
    731 						pq[idx[i]].push({U / L + 1, A - (f2 - f1)});
    732 						break;
    733 					}
    734 				} else if (sz(pq[idx[i]]) == 0) {
    735 					pq[idx[i]].push({cost[i], 1});
    736 					break;
    737 				}
    738 			}
    739 		}
    740 		int q;
    741 		cin >> q;
    742 		vector<pi> queries(q);
    743 		for (int i = 0; i < q; i++) {
    744 			cin >> queries[i][0];
    745 			queries[i][1] = i;
    746 		}
    747 		sort(all(queries));
    748 		vector<lint> ans(q);
    749 		lint A = 0, B = 0, pv = -1;
    750 		auto T = idx[2 * n - 2];
    751 		for (auto &[x, i] : queries) {
    752 			while (sz(pq[T]) && pq[T].top()[0] <= x) {
    753 				auto [point, slope] = pq[T].top();
    754 				pq[T].pop();
    755 				B += A * (point - pv);
    756 				pv = point;
    757 				A += slope;
    758 			}
    759 			ans[i] = (x - pv) * A + B;
    760 		}
    761 		for (auto &v : ans)
    762 			cout << v << "\n";
    763 	}
    764 }
    765 ```