...

#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";
    }
}

...

#include <bits/stdc++.h>

#define inf 1e9

struct node {
    int id;
    int p;
    int c; // c == inf to put it after the module if they have the same position

    node(int _id, int _p, int _c = inf) {
        id = _id;
        p = _p;
        c = _c;
    }
};

bool compare(node n1, node n2) {
    if (n1.p == n2.p) {
        return n1.c < n2.c;
    }

    return n1.p < n2.p;
}

using namespace std;

vector<string> solve() {
    //freopen("c.txt", "r", stdin);

    int n, m, k;

    cin>>n>>m>>k;
    vector<node> v;
    int cap[m][n];
    memset(cap, -1, sizeof cap);

    unordered_map<string, int> module_id_per_name;
    vector<string> module_name_per_id(n);
    string s;
    int c, p;
    int id = -1;
    for (int i=0 ; i<n ; i++) {
        cin>>s>>c>>p;
        module_id_per_name[s] = ++id;
        module_name_per_id[id] = s;
        v.push_back(node(id, p, c));
    }

    int num;
    for (int i=0 ; i<m ; i++) {
        cin>>num>>p;
        num--;
        v.push_back(node(num, p));
    }

    for (int i=0 ; i<k ; i++) {
        cin>>num>>s>>c;
        num--;
        cap[num][module_id_per_name[s]] = c;
    }

    sort(v.begin(), v.end(), compare);

    stack<node> st;
    stack<node> st2;

    n = v.size();
    for (int i = 0 ; i<n ; i++) {
        if (v[i].c == inf) { // virus
            int vid = v[i].id;
            while(!st.empty()) {
                node t = st.top();
                int mid = t.id;
                int vc = cap[vid][mid];
                if (vc == -1) { // can't collide
                    st2.push(t);
                    st.pop();
                } else {
                    int mc = t.c;
                    if (vc == mc) {
                        st.pop();
                        break;
                    } else if (vc < mc) {
                        st.top().c -= vc;
                        break;
                    } else {
                        st.pop();
                    }
                }
            }

            while(!st2.empty()) {
                st.push(st2.top());
                st2.pop();
            }
        } else {
            st.push(v[i]);
        }
    }

    vector<string> ans;
    while(!st.empty()) {
        ans.push_back(module_name_per_id[st.top().id]);
        st.pop();
    }
    return ans;
}

int main() {
    auto a = solve();
    cout << a.size() << endl;
    for(auto &u:a){
        cout << u << " ";
    }
    return 0;
}

...

#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 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 = 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() {
    // freopen("input.txt", "r", stdin);
    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 base on the HLD decompositions of the tree for each node what are 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) + 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;
}