...

#include<bits/stdc++.h>
using namespace std;

int main() {
    const string suffix = "@odoo.com";
    string s; cin >> s;

    int last_pos_at = s.find_last_of('@');

    if(s.size() < suffix.size()) {cout << "no\n"; return 0; }
    if(last_pos_at == string::npos) {cout << "no\n"; return 0;}
    if(last_pos_at < 2 || last_pos_at > 4) {cout << "no\n"; return 0;}
    if(s.substr(last_pos_at) != suffix) {cout << "no\n"; return 0; }
    
    for(int i = 0; i < last_pos_at; i++) {
        if(s[i] < 'a' || s[i] > 'z') {cout << "no\n"; return 0; }
    }

    cout << "yes\n";
}

...

#include<bits/stdc++.h>
using namespace std;

int main() {
    int T; cin >> T;
    const string odoo = "ODOO";
    while(T--) {
        string s; cin >> s;

        int ans = INT_MAX;
        for(int i = 0; i + 3 < s.size(); ++i) {
            int diff = (
                (s[i] != odoo[0]) + 
                (s[i + 1] != odoo[1]) +
                (s[i + 2] != odoo[2]) +
                (s[i + 3] != odoo[3])
            );
            ans = min(ans, diff);
        }
        cout << ans + s.size() - 4 << "\n";
    }
}

The idea is to sort the modules by position in a decreasing order and the viruses by position in an increasing order.You iterate over the modules, for each module we iterate over the viruses, if they collide (module position <= virus position) and the virus capacity is greater or equal to the module capacity, the module is dead. The virus is also dead, if the capacities are equal else, the module capacity is decreased by the virus capacity (the virus is dead) and continues the path to the server.

from collections import defaultdict

def solve():
    n, m, q = map(int, input().split())
    modules = []
    viruses = []
    virusCapacities = defaultdict(dict)

    for _ in range(n):
        name, capacity, position = input().split()
        modules.append((name, int(capacity), int(position)))

    for _ in range(m):
        id, position = map(int, input().split())
        viruses.append((id, position))

    for _ in range(q):
        virusId, moduleName, capacity = input().split()
        virusCapacities[int(virusId)][moduleName] = int(capacity)

    modules = sorted(modules, key=lambda x: x[2], reverse=True)
    viruses = sorted(viruses, key=lambda x: x[1])

    ans = []

    for moduleName, moduleCapacity, modulePosition in modules:
        passed = True
        for virusId, virusPosition in viruses:
            if virusPosition < modulePosition or moduleName not in virusCapacities.get(virusId, dict()):
                continue
            
            virusCapacity = virusCapacities[virusId][moduleName]
            if moduleCapacity == virusCapacity:
                passed = False
                del virusCapacities[virusId]
                break
            elif moduleCapacity < virusCapacity:
                passed = False  
                break
            else:
                del virusCapacities[virusId]
                moduleCapacity -= virusCapacity

        if passed:
            ans.append(moduleName)

    return ans
   

if __name__ == "__main__":
    a = solve()
    print(len(a))
    print(*a)

It's easy to notice that if a number x of servers can finish the tasks within the time limit $$$x + 1$$$ will be able to do this too, as we want to get the minimum number of servers this becomes a classic problem that we use binary search.

Now we just need to do the validation function of the binary search, in the problem, all the tasks need to be started in order, so we just need to simulate the process of allocating the next task to the server that will be free first. To do this in a fast way we can use a priority queue to help us.

The final complexity will be $$$n * log(n) * log (n)$$$.

#include<bits/stdc++.h>
using namespace std;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << "{"; for (typename vector<T>::const_iterator vi = v.begin(); vi != v.end(); ++vi) { if (vi != v.begin()) os << ", "; os << *vi; } os << "}"; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { os << '(' << p.first << ", " << p.second << ')'; return os; }
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

#define optimize ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"

#define fi first 
#define se second 
#define pb push_back

#define all(x) x.begin(),x.end()
#define ms(x,a) memset(x,a,sizeof(x))

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

#define mod 1000000007LL
#define MAXN 200010

/* -------------------------------- Solution starts below -------------------------------- */

ll N, T;
ll A[MAXN];

bool check(ll m) { 
    
    priority_queue<ll, vector<ll>, greater<ll>> pq;

    for(int i = 0; i < m; i++) {
        pq.push(0);
    }

    for(int i = 0; i < N; i++) {
        ll x = pq.top();
        pq.pop();

        if(x + A[i] > T) return false;

        pq.push(x + A[i]);
    }

    return true;
}

void solve() {

    ll l = 1, r = MAXN;

    while(l < r) {
        ll m = (l + r) / 2;

        if( check(m) )  r = m;
        else            l = m + 1;
    }

    if(l == MAXN) {
        l = -1;
    }

    cout << l << endl;
}

int main() {

	optimize;
	
    cin >> N >> T;

    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

	solve();
    
	return 0;
}

We want to calculate the maximum prefix sum for every subarray (prefix can be empty). To calculate prefix sum for just one subarray we start from the begining and loop over the subarray , we incremenet the current sum and we maximise over all sums. We can use this idea to make it more general, if we consider that sum from $$$l$$$ to $$$r$$$ is equal to $$$suff[l]-suff[r+1]$$$ ($$$suff$$$ is the suffix sum of the whole array$. If we fix the $$$l$$$ now , we will only consider $$$r$$$ as variable. Since starting from $$$l$$$ and going right will only increase the prefix sum then the prefix sum sequecnce will be in this form $$$a,a,a,b,b,b,c,c,d,d,d,d..$$$ where $$$a\lt b \lt c \lt d...$$$, since $$$l$$$ is fixed we can convert this sequence into a sequence of $$$rs$$$ then it will look like this $$$suff[l+1]...,suff[r1+1]....,suff[r2+1]...,suff[r3+1]...$$$ where $$$suff[l+1] > suff[r1+1] > suff[r2+1]..$$$ and $$$l \lt r1 \lt r2 ..$$$. So to get the answer we can keep always a sorted stack of the values where we pop from top the values that are greater than the current suffix to keep it always sorted and we update the sum accordingly it depends on in how many positions is the removed/added suffix is the maximum.

// Mtaylor
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define endl '\n';

typedef long long ll;
const int N = 3e5 + 5;

int t;
int n;
ll a[N];
ll sum[N];
vector<int> p;
void test_case() {
    cin >> n;
    p.clear();
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll s = 0;
    sum[n] = 0;
    p.pb(n);
    ll cur = 0;
    ll ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        s += a[i];
        sum[i] = s;
        while (p.size() && sum[p.back()] > s) {
            int y = p.back();
            p.pop_back();
            int x = -1;
            if (p.size()) {
                x = p.back();
            }
            if (x != -1) {
                cur -= sum[y] * (x - y);
            } else {
                cur -= sum[y] * (n + 1 - y);
            }
        }
        int x = -1;
        if (p.size()) {
            x = p.back();
        }
        if (x != -1) {
            cur += sum[i] * (x - i);
        } else {
            cur += sum[i] * (n + 1 - i);
        }
        p.push_back(i);
        ans -= cur;
        ans += sum[i] * (n - i + 1);
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        test_case();
    }
    return 0;
}

...

#include <bits/stdc++.h>
using namespace std;

#define int long long
int n, k, q;
struct segmentTree{
        vector<int> values;
        int sz = 1;
        void init(int n){
                while(sz < n) sz *= 2;
                values.resize(2 * sz, 1);
        }
        void set(int i, int v, int x, int lx, int rx){
                if(rx - lx == 1){
                        values[x] = v % k;
                        return;
                }
                int m = (lx + rx) >> 1;
                if(i < m)
                        set(i, v, 2 * x + 1, lx, m);
                else
                        set(i, v, 2 * x + 2, m, rx);

                values[x] = values[2 * x + 1] * values[2 * x + 2] % k;
        }
        void set(int i, int v){
                set(i, v, 0, 0, sz);
        }

        int ans(int x, int lx, int rx, int ai){
                if (rx - lx == 1){
                        return lx;
                }
                int m = (lx + rx) >> 1;
                if (values[2 * x + 1] * ai % k == 0){
                        return ans(2 * x + 1, lx, m, ai);
                }
                return ans(2 * x + 2, m, rx, ai * values[2 * x + 1] % k);
        }
        int ans(int x){
                if (x % k == 0)
                        return 0;
                if (values[0] * x % k != 0)
                        return -1;
                return ans(0, 0, sz, x);
        }
};

const int N = 2e5 + 10;
vector<int> adj[N];
int ans[N], a[N];
vector<pair<int,int>> updates[N];
segmentTree st;

void dfs(int node, int p){
        for (auto [i, y] : updates[node]){
                st.set(i, y);
        }
        ans[node] = st.ans(a[node]);
        for(int ch : adj[node]){
                if(ch != p)
                        dfs(ch, node);
        }
        for (auto [i, y] : updates[node]){
            st.set(i, 1);
        }
}
int32_t main() {
        cin.tie(0);
        cin.sync_with_stdio(0);

        cin>>n>>k>>q;
        for(int i = 0; i < n; i++){
                cin>>a[i]; a[i] %= k;
        }
        for(int i = 1; i < n; i++){
                int p; cin>>p; --p;
                adj[p].push_back(i);
        }
        for(int i = 1; i <= q; i++){
                int x, y;
                cin>>x>>y;
                updates[x - 1].push_back({i, y});
        }
        st.init(q + 10);
        dfs(0, 0);
        for(int i = 0; i < n; i++){
                cout<<ans[i]<<' ';
        }
}

...

v_pr = []
v_bonus = []
adj = []
query = []
offline = []
ans = []
added = []
parent = []

class Line:
  def __init__(self, m, c):
    self.m = m
    self.c = c


class CHTPersistent:
  def __init__(self):
    self.hull = []
    self.SZ = 0
    self.version_idx = []
    self.version_sz = []

  def inter(self, t1, t2):
    ret = (t2.c - t1.c)/(t1.m - t2.m)
    return ret

  def add2(self, curr):
    self.version_sz.append(self.SZ)

    if self.SZ > 1:
      s = 0
      e = self.SZ-1

      while s < e:
        p = (s+e)//2

        temp = self.hull[p+1][-1]
        temp2 = self.hull[p][-1]

        point = self.inter(temp, temp2)
        point2 = self.inter(temp, curr)

        if point < point2:
          s = p+1
        else:
          e = p

      self.SZ = s+1
    

    if len(self.hull) == self.SZ:
      x = []
      self.hull.append(x)

    self.hull[self.SZ].append(curr)
    self.version_idx.append(self.SZ)
    self.SZ+=1

  def add(self, m, c):
    self.add2(Line(m, c))

  def query(self, find):
    s = 0
    e = self.SZ-1

    while s < e:
      p = (s+e)//2

      point = self.inter(self.hull[p][-1], self.hull[p+1][-1])
      if point < find:
        s = p+1
      else:
        e = p

    ret = (self.hull[s][-1].m * find) + self.hull[s][-1].c
    return ret
  

  def rollback(self):
    self.SZ = self.version_sz[-1]
    self.version_sz.pop()
    self.hull[self.version_idx[-1]].pop()
    self.version_idx.pop()

  def size(self):
    return self.SZ

cht = CHTPersistent()

def dfs(u):
  while u != -1:
    if added[u] == False:
      cht.add(v_pr[u], v_bonus[u])

      for q_id in offline[u]:
        d = query[q_id]
        ans[q_id] = cht.query(d)

      added[u] = True

    if len(adj[u]) > 0:
      v = adj[u][-1]
      adj[u].pop()
      u = v
    else:
      cht.rollback()
      u = parent[u]

def main():
  txt = input().split()
  n = int(txt[0])
  q = int(txt[1])

  for i in range(n):
    adj.append([])
    v_pr.append(0)
    v_bonus.append(0)
    offline.append([])
    added.append(False)
    parent.append(0)

  for i in range(q):
    ans.append(0)

  root = -1

  for i in range(n):
    txt = input().split()

    idd = int(txt[0])
    pid = int(txt[1])
    pr = int(txt[2])
    bonus = int(txt[3])

    idd -= 1
    pid -= 1
    v_pr[idd] = pr
    v_bonus[idd] = bonus
    if pid == -1:
      root = idd
    else :
      adj[pid].append(idd)

    parent[idd] = pid

  for i in range(q):
    txt = input().split()
    idd = int(txt[0])
    d = int(txt[1])

    idd -= 1
    query.append(d)
    offline[idd].append(i)

  dfs(root)

  for i in range(q):
    print(ans[i])
	
if __name__ == "__main__":
  main()

To solve this problem, we will store in segment tree of sets based on the HLD decompositions of the tree for each node the indices of the cycle $$$i$$$ such that the node is in the path between nodes in positions $$$i$$$ and $$$i+1$$$. We can use a data structure to calculate the sum of lengths of paths between every consecutive nodes in the cycle (Fenwick tree is better since it's faster in practice). Now to get the answer , we will first query the hld seg tree to get the first index $$$i$$$ after $$$p$$$ in the cycle such that $$$u$$$ is in the path between $$$p$$$ and $$$p+1$$$. The total sum is then equal to $$$ Rangesum(p,i-1) + dist(v[i],u)$$$ so it represents all the paths to go fully and the last path we only take the distance to reach the node.

// Mtaylor
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define endl '\n';
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
typedef long long ll;
const int N = 1e5 + 5;
const int E = 1e6 + 5;

#define neig(u, v, e, g) \
    for (int e = g.head[u], v; ~e && ((v = g.to[e]), 1); e = g.nxt[e])

class ADJ {
   public:
    int head[E], to[E], nxt[E], n, edgcnt = 0;
    ll cst[E];

    void addEdge(int a, int b, int c = 0) {
        nxt[edgcnt] = head[a];
        head[a] = edgcnt;
        to[edgcnt] = b;
        cst[edgcnt] = c;
        edgcnt++;
    }

    void addBiEdge(int a, int b, int c = 0) {
        addEdge(a, b, c);
        addEdge(b, a, c);
    }
    void init(int _n) {
        n = _n;
        memset(head, -1, n * sizeof(head[0]));
        edgcnt = 0;
    }
} adj;

set<int> tree[4 * N];
int n, k, q;
int v[N];
int t, p, u;
set<int>::iterator it;
int getVal(int id, int k) {
    if (!tree[id].size()) return -1;

    it = tree[id].lower_bound(k);
    if (it != tree[id].end()) {
        return *it;
    }
    return *tree[id].begin();
}

int mrg(int x, int y, int k) {
    if (x == -1 || y == -1) return max(x, y);
    if (x >= k && y >= k) {
        return min(x, y);
    }
    if (x < k && y < k) {
        return min(x, y);
    }
    return max(x, y);
}

int queryPosition(int qp, int k, int id = 0, int ns = 0, int ne = n - 1) {
    int rs = getVal(id, k);
    if (ns == ne) {
        return rs;
    }
    int l = 2 * id + 1;
    int r = l + 1;
    int md = ns + (ne - ns) / 2;
    if (qp <= md) {
        rs = mrg(rs, queryPosition(qp, k, l, ns, md), k);
    } else {
        rs = mrg(rs, queryPosition(qp, k, r, md + 1, ne), k);
    }
    return rs;
}

void updateRange(int qs, int qe, int p, int to_ins, int id = 0, int ns = 0,
                 int ne = n - 1) {
    if (qs > ne || qe < ns) return;
    if (qs <= ns && qe >= ne) {
        if (to_ins) {
            tree[id].insert(p);
        } else {
            tree[id].erase(p);
        }
        return;
    }
    int l = 2 * id + 1;
    int r = l + 1;
    int md = ns + (ne - ns) / 2;
    updateRange(qs, qe, p, to_ins, l, ns, md);
    updateRange(qs, qe, p, to_ins, r, md + 1, ne);
}

class HLD {
   public:
    vector<int> par, sze, dpth, ndToIdx, chHead, heavyChld, idxToNd;
    int n, curPos;
    HLD() {}
    void run(ADJ &adj) {
        n = adj.n;
        curPos = 0;
        par.assign(n, -1);
        sze.assign(n, 0);
        dpth.assign(n, 0);
        ndToIdx.assign(n, 0);
        chHead.assign(n, 0);
        heavyChld.assign(n, 0);
        idxToNd.assign(n, 0);
        calcsz(0, adj);
        HLD_util(0, adj);
    }

    void calcsz(int u, ADJ &adj) {
        heavyChld[u] = -1;
        sze[u] = 1;
        int mx = 0, mxv;
        neig(u, v, e, adj) {
            if (par[u] == v) continue;
            par[v] = u;
            dpth[v] = dpth[u] + 1;
            calcsz(v, adj);
            if (sze[v] > mx) {
                mx = sze[v];
                mxv = v;
            }
            sze[u] += sze[v];
        }
        if (mx * 2 > sze[u]) {
            heavyChld[u] = mxv;
        }
    }

    void HLD_util(int u, ADJ &adj, int c = 0) {
        if (u == -1) return;
        idxToNd[curPos] = u;
        ndToIdx[u] = curPos++;
        chHead[u] = c;
        HLD_util(heavyChld[u], adj, c);
        neig(u, v, e, adj) {
            if (v == par[u]) continue;
            if (v == heavyChld[u]) continue;
            HLD_util(v, adj, v);
        }
    }
    int lca(int u, int v) {
        while (chHead[u] != chHead[v]) {
            if (dpth[chHead[v]] > dpth[chHead[u]]) swap(u, v);
            u = par[chHead[u]];
        }
        if (dpth[u] > dpth[v]) swap(u, v);
        return u;
    }
    int dist(int u, int v) { return dpth[u] + dpth[v] - 2 * dpth[lca(u, v)]; }
    // make sure to update the return type based on the type of the segment
    // tree
    int query(int u, int k) { return queryPosition(ndToIdx[u], k); }

    void update(int u, int v, int p, int to_insert) {
        while (chHead[u] != chHead[v]) {
            if (dpth[chHead[v]] > dpth[chHead[u]]) {
                swap(u, v);
            }
            updateRange(ndToIdx[chHead[u]], ndToIdx[u], p, to_insert);
            u = par[chHead[u]];
        }
        if (dpth[u] > dpth[v]) {
            swap(u, v);
        }
        updateRange(ndToIdx[u], ndToIdx[v], p, to_insert);
    }
} hld;
template <typename T>
class FenwickTree {
   public:
    vector<T> tree;
    int n;
    void init(int n) {
        tree.assign(n + 2, 0);
        this->n = n;
    }
    T mrg(T &x, T &y) { return x + y; }

    void upd(int x, T v) {
        for (; x <= n; x += (x) & (-x)) {
            tree[x] = mrg(tree[x], v);
        }
    }
    T getprefix(int x) {
        if (x <= 0) return 0;
        T rs = 0;
        for (; x; x -= (x) & (-x)) {
            rs = mrg(rs, tree[x]);
        }
        return rs;
    }
    T getrange(int l, int r) { return getprefix(r) - getprefix(l - 1); }
};
FenwickTree<ll> ft;

void solve_1() {
    for (int i = 0; i < q; i++) {
        cin >> t >> p >> u;
        p--;
        u--;
        if (t == 1) {
            v[p] = u;
        } else {
            if (v[0] == u) {
                cout << 0 << endl;
            } else {
                cout << -1 << endl;
            }
        }
    }
}

void solve_2() {
    for (int i = 0; i < q; i++) {
        cin >> t >> p >> u;
        p--;
        u--;
        if (t == 1) {
            v[p] = u;
        } else {
            if (hld.dist(v[0], u) + hld.dist(v[1], u) == hld.dist(v[0], v[1])) {
                cout << hld.dist(v[p], u) << endl;
            } else {
                cout << -1 << endl;
            }
        }
    }
}

void solve() {
    for (int i = 0; i < q; i++) {
        cin >> t >> p >> u;
        --u, --p;
        if (t == 1) {
            int d = hld.dist(v[p], v[(p + 1) % k]);
            ft.upd(p + 1, -d);
            hld.update(v[p], v[(p + 1) % k], p, 0);

            int b = (p + k - 1) % k;
            d = hld.dist(v[p], v[b]);
            hld.update(v[b], v[p], b, 0);
            ft.upd(b+1, -d);
            v[p] = u;
            d = hld.dist(v[p], v[(p + 1) % k]);
            ft.upd(p + 1, d);
            hld.update(v[p], v[(p + 1) % k], p, 1);
            d = hld.dist(v[p], v[b]);
            ft.upd(b+1, d);
            hld.update(v[b], v[p], b, 1);
        } else {
            int pos = hld.query(u, p);
            if (pos == -1) {
                cout << -1 << endl;
                continue;
            }
            ll dist = hld.dist(v[pos], u);

            if (pos >= p) {
                dist += ft.getrange(p + 1, pos);
            } else {
                dist += ft.getrange(p + 1, k);
                dist += ft.getprefix(pos);
            }
            cout << dist << endl;
        }
    }
}

void test_case() {
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        cin >> v[i];
        --v[i];
    }
    adj.init(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj.addBiEdge(u, v);
    }
    ft.init(k + 1);
    hld.run(adj);
    for (int i = 0; i < k; i++) {
        hld.update(v[i], v[(i + 1) % k], i, 1);
        ft.upd(i + 1, hld.dist(v[i], v[(i + 1) % k]));
    }
    cin >> q;
    if (k == 1) {
        solve_1();
    } else if (k == 2) {
        solve_2();
    } else {
        solve();
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while (T--) {
        test_case();
    }
    return 0;
}