Codeforces Round 966 (Div. 3) Разбор

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3611
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

№	Пользователь	Вклад
1	Qingyu	163
2	adamant	149
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	135
7	YuukiS	135
9	chromate00	134
10	soullless	132

2000A - Первостепенная задача

Разбор

Решение

for _ in range(int(input())):
    a = int(input())
    if 102 <= a <= 109 or 1010 <= a <= 1099:
        print("YES")
    else:
        print("NO")

2000B - Рассадка в автобусе

Идея: myav

Разбор

Решение

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin >> n;
    vector<int>a(n);
    for(auto &i : a) cin >> i;
    int left = a[0], right = a[0];
    for(int i = 1; i < n; i++){
        if(a[i] + 1 == left) left = a[i];
        else if(a[i] - 1 == right) right = a[i];
        else {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}
 
int main(){
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

2000C - Числовой шаблон строки

Идея: myav

Разбор

Решение

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    m = int(input())
    for _ in range(m):
        m_1 = {}
        m_2 = {}
        s = input().strip()
        if len(s) != n:
            print("NO")
            continue
 
        ok = True
        for j in range(n):
            if s[j] not in m_1 and a[j] not in m_2:
                m_1[s[j]] = a[j]
                m_2[a[j]] = s[j]
            elif (s[j] in m_1 and m_1[s[j]] != a[j]) or (a[j] in m_2 and m_2[a[j]] != s[j]):
                ok = False
                break
        print("YES" if ok else "NO")
 
t = int(input())
for _ in range(t):
    solve()

2000D - Right Left Wrong

Идея: Vladosiya

Разбор

Решение

def solve():
    n = int(input())
    a = [0]
    for x in input().split():
        x = int(x)
        a.append(a[-1] + x)
    s = input()
    ans = 0
    l = 0
    r = n - 1
    while r > l:
        while l < n and s[l] == 'R':
            l += 1
        while r >= 0 and s[r] == 'L':
            r -= 1
        if l < r:
            ans += a[r + 1] - a[l]
            l += 1
            r -= 1
    print(ans)
 
t = int(input())
for _ in range(t):
    solve()

2000E - Фотосессия для горилл

Идея: Vladosiya

Разбор

Решение

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
#define MAXW 200200
#define MAXNM 200200
 
int n, m, k, w, p;
int arr[MAXW], prr[MAXNM];
 
static inline int calcc(int i, int j) {
    int upr = min(i, n - k);
    int leftr = min(j, m - k);
    int upl = max(-1LL, i - k);
    int leftl = max(-1LL, j - k);
    return (upr - upl) * (leftr - leftl);
}
 
void build() {
    sort(arr, arr + w);
    reverse(arr, arr + w);
    p = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            prr[p++] = calcc(i, j);
    sort(prr, prr + p);
    reverse(prr, prr + p);
}
 
int solve() {
    int sum = 0;
    for (int i = 0; i < w; ++i)
        sum += prr[i] * arr[i];
    return sum;
}
 
signed main() {
    int t; cin >> t;
    while (t--) {
        cin >> n >> m >> k >> w;
        for (int i = 0; i < w; ++i)
            cin >> arr[i];
        build();
        cout << solve() << endl;
    }
}

2000F - Закрась строки и столбцы

Идея: ibraevdmitriy

Разбор

Решение

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 1e9));
    dp[0][0] = 0;
    for (int i = 0; i < n; ++i) {
        int x = a[i], y = b[i];
        int xy = x + y;
        int cost = 0;
        for (int j = 0; j <= xy; ++j) {
            for (int j1 = 0; j1 + j <= k; ++j1) {
                dp[i + 1][j1 + j] = min(dp[i + 1][j1 + j], dp[i][j1] + cost);
            }
            if (j < xy) {
                if (x >= y) {
                    x--, cost += y;
                } else {
                    y--, cost += x;
                }
            }
        }
    }
    cout << (dp[n][k] == 1e9 ? -1 : dp[n][k]) << '\n';
}
 
int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

2000G - Звонок во время пути

Идея: ibraevdmitriy

Разбор

Решение

#include <iostream>
#include <vector>
#include <set>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    int t0, t1, t2;
    cin >> t0 >> t1 >> t2;
    vector<vector<vector<int>>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v, l1, l2;
        cin >> u >> v >> l1 >> l2;
        u--, v--;
        g[u].push_back({v, l1, l2});
        g[v].push_back({u, l1, l2});
    }
    set<pair<int, int>> prq;
    prq.insert({t0, n - 1});
    for (int i = 0; i + 1 < n; ++i) {
        prq.insert({-1e9, i});
    }
    vector<int> dist(n, -1e9);
    dist[n - 1] = t0;
    while (!prq.empty()) {
        auto p = *prq.rbegin();
        prq.erase(p);
        int d = p.first, u = p.second;
        for (auto e: g[u]) {
            int v = e[0], l1 = e[1], l2 = e[2];
            int d1 = (d - l1 >= t2 || d <= t1) ? d - l1 : d - l2;
            if(d1 == d - l2) d1 = max(d1, t1 - l1);
            if (dist[v] < d1) {
                prq.erase({dist[v], v});
                dist[v] = d1;
                prq.insert({d1, v});
            }
        }
    }
    cout << (dist[0] >= 0 ? dist[0] : -1) << '\n';
}
 
int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

2000H - Ксюша и загруженное множество

Идея: ibraevdmitriy

Разбор

Решение

#pragma GCC optimize("O3,unroll-loops")
 
#include <bits/stdc++.h>
 
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> ipair;
 
#define INF 1'000'000'009
#define MAXN 200200
#define MAXMEM 5'000'000
#define MAXLEN 2'000'100
 
#define X first
#define Y second
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
struct node {
    node *lv = nullptr, *rv = nullptr;
    ipair key;
    int prior;
    int minl = INF;
    
    node(const ipair& key) : key(key), prior(rng()), minl(key.Y) {}
};
 
static inline int minl(node *v) {
    return (v == nullptr ? INF : v->minl);
}
 
static inline void upd(node *v) {
    v->minl = min(v->key.Y, min(minl(v->lv), minl(v->rv)));
}
 
node *merge(node *s1, node *s2) {
    if (s1 == nullptr) return s2;
    if (s2 == nullptr) return s1;
    if (s1->prior > s2->prior) {
        s1->rv = merge(s1->rv, s2);
        upd(s1);
        return s1;
    } else {
        s2->lv = merge(s1, s2->lv);
        upd(s2);
        return s2;
    }
}
 
pair<node*, node*> split(node* &v, ipair x) {
    if (v == nullptr) {
        return {nullptr, nullptr};
    }
    if (v->key < x) {
        auto [s1, s2] = split(v->rv, x);
        v->rv = s1;
        upd(v);
        return {v, s2};
    } else {
        auto [s1, s2] = split(v->lv, x);
        v->lv = s2;
        upd(v);
        return {s1, v};
    }
}
 
int n, m;
int arr[MAXN];
node *mem = (node*)calloc(MAXMEM, sizeof(*mem));
node *mpos = mem;
node *root;
set<int> M;
 
// [l..r)
void add_seg(int l, int r) {
    if (l >= r) return;
    ipair p {r - l, l};
    auto [s1, s2] = split(root, p);
    node *v = mpos++;
    *v = node(p);
    root = merge(merge(s1, v), s2);
}
 
void rem_dek(node* &v, const ipair& x) {
    if (v == nullptr) return;
    if (v->key == x) {
        v = merge(v->lv, v->rv);
        if (v) upd(v);
        return;
    }
    if (v->key < x) rem_dek(v->rv, x);
    else rem_dek(v->lv, x);
    upd(v);
}
 
// [l..r)
void rem_seg(int l, int r) {
    if (l >= r) return;
    ipair p {r - l, l};
    rem_dek(root, p);
}
 
void add_val(int x) {
    auto it = M.lower_bound(x);
    int clsl = (it == M.begin() ? 0 : *prev(it));
    int clsr = (it == M.end() ? INF : *it);
    rem_seg(clsl + 1, clsr);
    add_seg(clsl + 1, x);
    if (clsr != INF) add_seg(x + 1, clsr);
    M.insert(x);
}
 
void rem_val(int x) {
    auto it = M.lower_bound(x);
    int clsl = (it == M.begin() ? 0 : *prev(it));
    int clsr = (next(it) == M.end() ? INF : *next(it));
    rem_seg(clsl + 1, x);
    rem_seg(x + 1, clsr);
    if (clsr != INF) add_seg(clsl + 1, clsr);
    M.erase(x);
}
 
int query(int k) {
    if (M.empty()) return 1;
    auto [s1, s2] = split(root, make_pair(k, -1));
    fprintf(stderr, "AMOGUS: %p, %p\n", s1, s2);
    int ans = min(*M.rbegin() + 1, minl(s2));
    root = merge(s1, s2);
    return ans;
}
 
void init() {
    root = nullptr;
    mpos = mem;
    M = {arr, arr + n};
    add_seg(1, *M.begin());
    for (auto it = M.begin(); next(it) != M.end(); ++it)
        add_seg(*it + 1, *next(it));
}
 
signed main() {
    int t; cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> arr[i];
        init();
        cin >> m;
        for (int j = 0; j < m; ++j) {
            char tp; cin >> tp;
            int x, k;
            switch (tp) {
            case '+':
                cin >> x;
                add_val(x);
                break;
            case '-':
                cin >> x;
                rem_val(x);
                break;
            case '?':
                cin >> k;
                cout << query(k) << " ";
                break;
            }
        }
        cout << endl;
    }
}

auto fitr = que.lower_bound(x); if(fitr == que.end()) cout << -1 << " "; else { int mini = INT_MAX; for(; fitr != que.end();) { mini = min(mini, *(fitr->second.begin())); fitr = next(fitr); } cout << mini << " "; }

#include <bits/stdc++.h> using namespace std; // Include necessary header files for ordered_set #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; // Define an ordered set typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // Define macros for convenience #define int long long #define f(i, a, b) for (int i = a; i < b; i++) #define rf(i, a, b) for (int i = a; i >= b; i--) #define vi vector<int> #define vpii vector<pair<int, int>> #define vvvi vector<vector<vector<int>>> #define vvi vector<vector<int>> #define vvpi vector<vector<pair<int, int>>> #define vb vector<bool> const int inf = 1e18; int n, m, t0, t1, t2; vvvi adj; int dijkstra(int src, int dest, int start_time) { vi dist(n + 1, inf); dist[src] = start_time; priority_queue<vi, vvi, greater<vi>> pq; pq.push({start_time, src}); int dur = t2 - t1; while (!pq.empty()) { vi curr = pq.top(); pq.pop(); int u = curr[1]; int time = curr[0]; if (time > dist[u]) continue; for (vi edge : adj[u]) { int v = edge[0]; int l1 = edge[1]; int l2 = edge[2]; int new_time = time + l1; if (time >= t1 && time < t2) { // Call is active if (dur >= l2) { // take l2 route new_time = time + l2; dur -= l2; } else { // take l2 route if (l2 < (t2 - time) + dur + l1) { new_time = time + l2; dur = 0; } else { // wait and take l1 route new_time = time + (t2 - time) + dur + l1; dur = 0; } } } else if (time <= t1 && t1 < new_time) { // Crosses into active call period if (dur >= l2) { // take l2 route new_time = time + l2; dur -= l2; } else { if (l2 < (t1 - time) + dur + l1) { // take l2 route new_time = time + l2; dur = 0; } else { // wait and take l1 route new_time = time + (t1 - time) + dur + l1; dur = 0; } } } if (new_time < dist[v]) { // Relaxation dist[v] = new_time; pq.push({new_time, v}); } } } return dist[dest]; } void solve() { cin >> n >> m; cin >> t0 >> t1 >> t2; adj = vvvi(n + 1); f(i, 0, m) { int u, v, l1, l2; cin >> u >> v >> l1 >> l2; adj[u].push_back({v, l1, l2}); adj[v].push_back({u, l1, l2}); } int low = 0, high = t0; int ans = -1; // binary on how late we can start our journey to reach on time while (low <= high) { int mid = low + (high - low) / 2; if (dijkstra(1, n, mid) <= t0) { ans = mid; low = mid + 1; } else { high = mid - 1; } } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int tc; cin >> tc; while (tc--) solve(); return 0; }

Комментарии (49)

Показать архивные | Написать комментарий?

Manish_Jangir

21 месяц назад, скрыть # |

can anyone pls tell why this code is getting a runtime error. for Problem D

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rf(i,a,b) for(ll i=b-1;i>=a;i--)

/* When a man learns to love he must bear the risk of hatred */
/* I don't know WTF am I doing */
/* Now I hate You */

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll t;cin>>t;
    while(t--){
        ll n;cin>>n;
        vector<ll> a(n);
        f(i,0,n){
            cin>>a[i];
        }
        string str; cin>>str;
        vector<ll> leftsig,rightsig;
        f(i,0,n){
            if(str[i]=='L')leftsig.push_back(i);
            else rightsig.push_back(i);
        }
        ll left = 0;
        ll right = rightsig.size()-1;
        ll sum = 0;
        
        while(left<leftsig.size() && right>=0 && leftsig[left]<rightsig[right]){
            sum += accumulate(a.begin()+leftsig[left],a.begin()+rightsig[right]+1,0LL);
            left++;
            right--;
        }
        cout<<sum<<endl;

    }   
    
}

And also the issue with the algo pls.

→ Ответить

scratch

21 месяц назад, скрыть # ^ |

← Rev. 2 →

consider the case where there are no 'R' in the string. in this scenario, your 'right' variable would be initialized with the value -1

edit : avoid using C++17 (GCC 7-32) and use C++20 (GCC 13-64) instead

you mean something like this -> n = 6, a(n) = 1 1 1 1 1 1 s = LLLLLL -> and the output should be 0 right. actually I checked this one already and it gives me 0 perfectly fine. Cause I'm checking the out of bound condition before using those

I admit I do not know much about C++17 (32-bit), but if I had to guess, this particular error might be occurring because your while loop condition:

while(left < leftsig.size() && right >= 0 && leftsig[left] < rightsig[right]) {

is not stopping after right >= 0 evaluates to false. Instead, it continues evaluating leftsig[left] < rightsig[right], which could cause an access violation if right is -1 and thus result in the error

you can fix it by choosing C++20 (GCC 13-64) as your compiler when you submit the code

https://mirror.codeforces.com/contest/2000/submission/276452095

TANMAY_1408

This solution will give tle as you are calculating sum of subarray again and again. Instead use prefix sum to get the sum of the subarray.

Ziad_Abdou

I need help

Can anyone tell me why my solution in proplem E got TLE when i write it in java , but when i write the same code in c++ i got AC

java solution --> Your text to link here...

c++ solution --> Your text to link here...

WOWWA

someone explain how to intuit the way they count it in problem E please.

itsraajjjuuuu

do u know diffrence array? to update values in range for 1d vector it can be used here to count for 2d vector then 2d prefix sum

arvindf232

← Rev. 3 →

+17

I am impressed by how treap is being casually used in a div3 contest editorial (problem H).

(Context: Of course I am well aware that this is not how most contestants solved, or are supposed to solve it, but rather make use of the (non-essential) constraints max <= 2e6. It is also clear that a fully online solution of this without the extra constraints will have to involve your favourite BBST. Though, I don't know how many people will get confused by the editorial. )

Dominater069

+33

They took the effort to explain the std::set part but not the treap part :)

yellow_13

If possible can you explain how to do it without treap? I was thinking of a solution where I can maintain an array where the indices represent the lengths of the free segments and the value at that index is the value of the left border of that segment, then I just need to find suffix minimums to answer any query. I was thinking of using segment tree for handling updates and suffix range queries, but I think that will TL because there is no bound on sum of $$$max(a_i)$$$ across all test cases and my time complexity would become $$$O(T\cdot max(a_i) \cdot\log{max(a_i)})$$$ in that case.

You can reuse the same segment tree. So initialise one segment tree with size max(a_i), at the end of each test case you undo all insertions.

I take that you already know how to "find first index in segment tree that is >= some value", but for others this can be handled by using a max-segment tree and a standard segment tree descend

Wry_0313

20 месяцев назад, скрыть # ^ |

I tried implementing this solution but I received TLE. Can you help me find out why this is happening? https://mirror.codeforces.com/contest/2000/submission/278601400

Your segment tree descent code is O(n). Read the segment tree before deciding going left or right, rather than just recur/

Hi I just reimplemented a log(n) descent. However, I am still getting TLE ;-;

https://mirror.codeforces.com/contest/2000/submission/278684047

I cannot find an obvious mistake. Try to run it in gym with more TL and see how close it is. If it is close to 3s, then it may simply be that recursive seg tree are too slow to pass. My solution that takes 1500ms in Kotlin is iterative.

noobcoder180

treap sounds like something you cover a pool with

lrvideckis

for E, I completely missed the n*m<=2e5 bound and coded a O(nlogn + mlogm + wlog(n*m)) solution

276188663

0mar

I also misread the n*m<=2e5 constraint, and I tried to code a bfs type solution starting from the center of the grid where we greedily visit cells in the graph that have the most subarrays containing them. I failed in the implementation, but is your solution idea similar?

yes, similar, that's pretty much what I did

bricked_

I got scared when I didn't see the n*m <= 2e5 condition and I immediately re-checked the problem statement :)

bkchodi

🆗

Harshvardhan_Acharya

H can be solved using segment tree. 276462150

stemdarrenyang

How can I report suspected cheating in this round?

Oleja123

The problem H has a beautiful solution using sqrt decomposition (It works slower than the author's solution, but it seems to me easier to understand and write). My example solution: https://mirror.codeforces.com/contest/2000/submission/276433907

harshith_04

Problem H Solution without any specific method/data structure but only logic — 276496494

I_love_GSNQK

what is the time complexity of this block?

Worst case is ~ $$$\sqrt {2 . 10^6}$$$. When the set has 2e6-1, 2e6-4, 2e6-8, 2e6-13, .... and the query is "? 1" ig

ckxian

Can someone explain me Problem F in detail? I saw shayan's vid but I keep getting lost. (I have a fair experience with dp)

olegmak

The hardest part of this problem is understanding optimal way of painting single rectangle. Like they say in editorial you must always choose to paint single column or row of minimum size. For example, if you have 3 by 4 rectangle you unpainted rectangle will change like this: 3x4 -> 3x3 -> 3x2 (or 2x3, does not matter) -> 2x2 -> 2x1 (or 1x2) -> 1x1 -> 0x0 Every transition will give you one score point (except for last which gives 2 points because we paint one row and one column at the same time). You perform this sequence of operations on the first rectangle, keep track on the number of operations (cnt1) and score (s), calculate recursively min. number of operations for the rest of the rectangles to achieve (k — s) score (cnt2), choose min(cnt1 + cnt2) after painting sequence is complete.

ProofByContradiction_

can someone explain, why the sample testcase 1 answer is 0. I think we can wait upto 19 minutes and then take the bus route 1 — 5 which will cost 30 minutes, and we will arrive on 5 at 49 minutes ?

You cannot ride a bus during entire phone call, not just start of it.

LightWave

Can anyone help me find out the test case for which 276261336 problem C (test case 18), failed ?. Appreciate any help thank you :)

27debowskijakub

I found this test case:

Test

1
3
0 0 1 
4
CBB
ACE
D
DD

which in my code returns:

Result

NO
NO
NO
NO

and in yours:

NO
YES
NO
NO

Hope it helps!

wsaleem

← Rev. 4 →

For problem G sample 1, can someone share the route which corresponds to a starting time of 0? From what I understand of the problem, there should be no solution and the answer should be -1. Maybe I am overlooking something. I am copying the sample below for convenience.

joaozao

In time 0, walk through the edge from 1 to 5. That will take 100 units of time, which fits in t0.

For Problem F, sample 6, reproduced below, can someone explain how the required 25 points can be obtained in 80 operations, as given in the sample solution?

akmeena5726

First we will completely fill the 2*9 and 4*3 rectangles. After this our score would be 18 and operations are 30. After this we will start filling the 8*10 rectangle in this order — 8, 8, 8, 7, 7, 6, 6. This would lead to a total score of 25 in 80 operations.

asharique22

did any one solved F using greedy?

rk0822

Can you tell me how 35 operations are required in last test case

4 18 5 4 8 5 8 3 6 2

Use entire first and last rectangle and then use rectangle which is having b = 3 to make the score 18

Can anyone please explain what's wrong in my approach of problem G. I applied binary search to find how late we can start to reach on time. What I'm doing in my modified dijkstra is that if I can take bus then then will take it but if I will get a call in between or currently on a call then I will take the best of wait till the call is finish and take bus or walk.

My Code

Can someone please explain me how are we getting 35 operations in last test case of sample? I am getting 36 operations to score 18 points.

Fill the 6 x 2 (score = 8 & operations = 12) rectangle and 5 x 4 rectangle (score = 9 & operations = 20) completely and one row of 8 x 3 rectangle (score = 1 & operations = 3). Therefore total operations and score would be 12 + 20 + 3 = 35 and 8 + 9 + 1 = 18 respectively.

Ahmed_Ashraf_f

Why am I not official in this round !!!

soicodoc10tin

In problem G, why did I get TLE when I used priority_queue but after switching to set<pair<int,int>> it became AC?

Pannka384

20 месяцев назад, скрыть # |

is it possible to solve problem H using a segment tree

Jose_17

7 недель назад, скрыть # |

H can solve with segment tree, kadane and walking in the seg. if x is in the set, the value in the segment is -inf else 1

Nastya_An

4 недели назад, скрыть # |

Solve H with using a segment tree:

Let's use that $$$a_i$$$ $$$\leq$$$ $$$C$$$, where $$$C=2*10^6$$$

Let's imagine an array $$$nxt$$$: if the set currently contains a number $$$i$$$, then $$$nxt[i]$$$ is equal to the number of elements starting with $$$i+1$$$ that are not in the set. That is, if the next higher number than $$$i$$$ in the set is $$$j$$$, then $$$nxt[i] = j - i - 1$$$. If there is no next number, then we must set it to $$$inf$$$ (or a number that is definitely sufficient for the problem, namely $$$2*10^6$$$). If the number $$$i$$$ is not in the set, then $$$nxt[i] = 0$$$.

Let's construct a segment tree for maximum on the array $$$nxt$$$.

Query responses are then processed as follows:

1) $$$nxt[i]$$$ can be updated by changing the value at a point in the segment tree, using std::set to maintain the set's elements and quickly find the next higher/lower element

2) answering a query is equivalent to finding the first element from the left in $$$nxt$$$ that is >= $$$k$$$. This is a standard problem that can be solved either using binsearch + prefix max queries using a segment tree, which will yield a $$$O(log^2 C)$$$ per query, or by descending the segment tree, which will yield $$$O(log C)$$$.

Also note that you can't reset the segment tree for each testcase, as this will result to $$$O(C*t)$$$ appearing in the asymptotics and exceeding the time limit. You can do it this way: after processing all queries, iterate through the set of remaining numbers and reset the segment tree at these positions. Then all changes will take a total of $$$O((n + q) * log C)$$$

It's $$$O((n + q) * log C)$$$

(you can see my solution for a better understanding)

Блог пользователя Vladosiya

🆗