/*
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1E18;
struct modify_online_subset_minimum{
vector<int> a, ans;
int l, r;
priority_queue<array<int, 4>, vector<array<int, 4>>, greater<array<int, 4>>> pq;
modify_online_subset_minimum(vector<int> a_, int l_, int r_) : l(l_), r(r_){
a = a_;
sort(a.begin(), a.end());
if(l == 0) pq.push({0, -1, -1, -1});
int val = 0;
for(int i = 0; i < a.size(); i++){
val += a[i];
if(i + 1 >= l && i + 1 <= r) pq.push({val, i, i, a.size()});
}
}
int operator[](int i){
while(i >= ans.size()){
if(pq.empty()) break;
auto [v, c, i, h] = pq.top(); pq.pop();
ans.push_back(v);
if(c == -1) continue;
if(i + 1 < h) pq.push({v - a[i] + a[i + 1], c, i + 1, h});
if(c > 0 && c < i) pq.push({v - a[c - 1] + a[c], c - 1, c, i});
}
return i < ans.size() ? ans[i] : inf;
}
};
void solve() {
int n, m, k; cin >> n >> m >> k;
vector<vector<int>> a(m);
for(int i = 0; i < n; i++){
int u, t; cin >> t >> u;
a[t - 1].push_back(u);
}
vector<modify_online_subset_minimum> all;
for(int i = 0; i < m; i++){
int l, r; cin >> l >> r;
all.push_back(modify_online_subset_minimum(a[i], l, r));
}
sort(all.begin(), all.end(), [&](auto& u, auto& v){
return u[1] - u[0] < v[1] - v[0];
});
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
int val = 0;
for(int i = 0; i < m; i++){
val += all[i][0];
if(all[i][0] == inf){
while(k--) cout << -1 << '\n';
return;
}
}
pq.push({val, -1, 0});
while(k--){
if(pq.empty() || pq.top()[0] >= inf){
cout << "-1\n";
continue;
}
auto [v, i, p] = pq.top();
pq.pop();
cout << v << '\n';
if(i != -1) pq.push({v + all[i][p + 1] - all[i][p], i, p + 1});
if(i + 1 < m) pq.push({v + all[i + 1][1] - all[i + 1][0], i + 1, 1});
if(p == 1 && i + 1 < m) pq.push({v + all[i + 1][1] - all[i + 1][0] + all[i][0] - all[i][1], i + 1, 1});
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5, inf = 1e18;
vector<int> adj[maxn];
int a[maxn], cnt[maxn][2], f[maxn][2], n, k;
struct Data{
int type, v, v1;
};
void dfs(int u){
vector<Data> sorted;
//0 có nối với cha.
//1 không nối với cha
//cnt[v][1] >= cnt[v][0] luôn đúng
//f[v][1] >= f[v][0] luon đúng
for(int v: adj[u]){
dfs(v);
cnt[u][0] += cnt[v][1];
cnt[u][1] += cnt[v][1];
if(cnt[v][0] == cnt[v][1]){
f[u][0] += f[v][0];
f[u][1] += f[v][0];
sorted.push_back({0, a[v], f[v][1] - f[v][0]});
}else{ //chọn cnt[v][1] luôn tối ưu. nếu có thể thay thế = cnt[v][0].
f[u][0] += f[v][1];
f[u][1] += f[v][1];
sorted.push_back({1, min(0LL, f[v][0] + a[v] - f[v][1]), inf});
}
}
sort(sorted.begin(), sorted.end(), [&](Data a, Data b){
if(a.type != b.type) return a.type < b.type;
if(a.type == 1) return a.v < b.v;
return (a.v - a.v1 < b.v - b.v1);
});
for(int i = 0;i < sorted.size(); i++){
if(i < k - 1){
cnt[u][0] += !sorted[i].type;
f[u][0] += sorted[i].v; //f[u][0]
}else{
if(!sorted[i].type) f[u][0] += sorted[i].v1; //a[v] - f[v][1] + f[v][0] .//minimize; vậy sẽ maxumize khi
}
}
for(int i = 0;i < sorted.size(); i++){
if(i < k){
cnt[u][1] += !sorted[i].type;
f[u][1] += sorted[i].v;
}else{
if(!sorted[i].type) f[u][1] += sorted[i].v1;
}
}
}
void solve(){
cin >> n >> k;
for(int i = 2; i <= n; i++){
int p; cin >> p >> a[i];
adj[p].push_back(i);
}
dfs(1);
cout << cnt[1][1] << " " << f[1][1];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
}*/
/*
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e4 + 5, offset = 5e4, inf = 1e18;
int n, k, ans, sum_cnt;
int sz[maxn], cnt[2 * maxn], del[maxn];
vector<pair<int, int>> adj[maxn];
void dfs(int u, int p){
sz[u] = 1;
for(auto [v, w]: adj[u]){
if(v == p || del[v]) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
int find_centroid(int u, int p, int targ){
for(auto [v, w]: adj[u]){
if(v != p && !del[v] && sz[v] > targ / 2) return find_centroid(v, u, targ);
}
return u;
}
void count(int u, int p, int cur_sum, int val) {
ans += sum_cnt;
for(auto [v, w]: adj[u]){
if(v == p || del[v]) continue;
int t = (w > val ? 1 : -1);
if(t == 1) sum_cnt -= cnt[offset - cur_sum];
else sum_cnt += cnt[offset - cur_sum + 1];
count(v, u, cur_sum + t, val);
if(t == 1) sum_cnt += cnt[offset - cur_sum];
else sum_cnt -= cnt[offset - cur_sum + 1];
}
}
void update(int u, int p, int cur, int val, int &mx, int &mn){
cnt[offset + cur]++;
mx = max(mx, offset + cur);
mn = min(mn, offset + cur);
if(cur <= 0) sum_cnt++;
for(auto [v, w]: adj[u]){
if(v != p && !del[v]) update(v, u, cur + (w > val ? 1 : -1), val, mx, mn);
}
}
void decompose(int u, int val){
dfs(u, 0);
int c = find_centroid(u, 0, sz[u]);
del[c] = true;
cnt[offset] = 1;
sum_cnt = 1;
int mx = offset, mn = offset;
for(auto [v, w]: adj[c]){
if(del[v]) continue;
int t = (w > val ? 1 : -1);
if(t == 1) sum_cnt -= cnt[offset];
else sum_cnt += cnt[offset + 1];
count(v, c, t, val);
if (t == 1) sum_cnt += cnt[offset];
else sum_cnt -= cnt[offset + 1];
update(v, c, t, val, mx, mn);
}
for(int i = mn; i <= mx; i++) cnt[i] = 0;
for(auto [v, _]: adj[c]) if(!del[v]) decompose(v, val);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n - 1; i++){
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int l = 0, r = 1e9, res = 1e9;
while(l <= r){
int mid = (l + r) / 2;
ans = 0;
for(int i = 1; i <= n; i++) del[i] = false;
decompose(1, mid);
if(ans >= k) res = mid, r = mid - 1;
else l = mid + 1;
}
cout << res;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
array<int, 2> get(string s){
s = ' ' + s + ' ';
vector<array<int,2>> dp(s.size());
int ptr = 0;
dp[0] = {0, 1};
for(int i = 1; i < s.size(); i++){
dp[i] = dp[i-1];
if(dp[i][0] < dp[ptr][0] + 1){
dp[i] = dp[ptr];
dp[i][0]++;
}else if(dp[i][0] == dp[ptr][0] + 1){
dp[i][1] += dp[ptr][1];
dp[i][1] -= (dp[i][1] >= mod ? mod : 0LL);
}
if(s[i] != s[i-1]){
ptr = i - 1;
}
}
return dp.back();
}
void solve(){
int n; cin >> n;
string s; cin >> s;
auto [u, v] = get(s);
cout << u << " " << v << "\n";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t--) solve();
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5 + 5;
int sz[maxn], dep[maxn], par[maxn], bad[maxn];
int tin[maxn], low[maxn], timer;
vector<int> adj[maxn];
pair<int, int> mk[maxn], mc[maxn];
bool brute(int u, int v, int n){
int start = 1;
while(start == u || start == v) start++;
queue<int> q;
q.push(start);
vector<int> vis(n + 1);
vis[start] = vis[u] = vis[v] = 1;
int cnt = 0;
while(q.size()){
int x = q.front(); q.pop(); cnt++;
for(int y : adj[x]) if(!vis[y]) vis[y] = 1, q.push(y);
}
return cnt < n - 2;
}
void dfs(int u, int p){
tin[u] = low[u] = ++timer;
dep[u] = dep[p] + 1;
par[u] = p;
sz[u] = 1;
mc[u] = {-1, -1}; mk[u] = {-1, -1};
for(int v: adj[u]){
if(v == p) continue;
if(tin[v]) low[u] = min(low[u], dep[v]);
else{
dfs(v, u);
sz[u] += sz[v];
low[u] = min(low[u], tin[v]);
mc[u] = max(mc[u], {low[v], sz[v]});
if(low[v] >= tin[u]) {
bad[u]++;
if(sz[v] > mk[u].first) mk[u] = {sz[v], mk[u].first};
else mk[u].second = max(mk[u].second, sz[v]);
}
}
}
}
void solve(){
int n, m; cin >> n >> m;
vector<pair<int, int>> canh;
for(int i = 0; i < m; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
canh.push_back({u, v});
}
dfs(1, 0);
int ans = 0;
for(auto [u, v]: canh){
if(tin[u] > tin[v]) swap(u, v);
if(par[v] == u){
bool ok = 0;
if(mc[v].first >= tin[u] && mc[v].second < n - 2) ok = 1;
int cbad = bad[u], csz = mk[u].first;
if(low[v] >= tin[u]){
cbad--;
if(sz[v] == csz) csz = mk[u].second;
}
if(cbad && csz < n - 2) ok = 1;
ans += ok;
}else ans += brute(u, v, n);
}
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
solve();
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e3 + 5, mod = 1e9 + 7;
int dp[maxn][maxn], pre[maxn][maxn],sum_dp[maxn],val[2*maxn],L[maxn],R[maxn],inv[maxn];
int binpow(int a, int b){
int res = 1;
while(b){
if(b & 1) res =res * a % mod;
a = a * a % mod;
b /= 2;
}
return res;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("BOAT.inp", "r", stdin);
// freopen("BOAT.out", "w", stdout);
int n; cin >> n;
int cnt = 0;
for(int i = 1; i <= n; i++){
cin >> L[i] >> R[i];
val[++cnt] = L[i];
val[++cnt] = R[i] + 1;
}
sort(val + 1, val + cnt + 1);
cnt = unique(val + 1, val + cnt + 1) - (val + 1);
for(int i = 1; i <= n; i++) inv[i] = binpow(i, mod - 2);
for(int i = 0; i <= cnt; i++) sum_dp[i] = 1;
for(int i = 1; i <= n; i++){
int idl = lower_bound(val + 1, val + cnt + 1, L[i]) - val;
int idr = lower_bound(val + 1, val + cnt + 1, R[i] + 1) - val;
for(int j = idl; j < idr; j++)
for(int k = 1; k <= i; k++) pre[j][k] = dp[j][k];
for(int j = idl; j < idr; j++){
int len = (val[j + 1] - val[j]);
dp[j][1] = (dp[j][1] + sum_dp[j-1] * len) % mod; //k = 1
for(int k = 2; k <= i; k++){ //k > 1
dp[j][k] = (dp[j][k] + pre[j][k - 1] * (len - k + 1) % mod * inv[k] % mod) % mod;
}
}
for(int j = 1; j < cnt; j++){
sum_dp[j] = sum_dp[j - 1];
for(int k = 1; k <= i; k++) sum_dp[j] = (sum_dp[j] + dp[j][k]) % mod;
}
}
int ans = 0;
for(int j = 1; j < cnt; j++){
for(int k = 1; k <= n; k++) ans = (ans + dp[j][k]) % mod;
}
cout << ans;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 30, maxm = 1e5 + 5, mod = 1e9 + 7;
int type[maxn], l[maxn], r[maxn];
vector<int> adj[maxn];
int dp[maxn][maxm], f[maxn][maxm];
int g(int u, int x);
int solve(int u, int from){
if(dp[u][from] != -1) return dp[u][from];
int res = 0;
if(type[u] == 0){
for(int v = l[u]; v <= r[u]; v++) res = (res + g(u, v)) % mod;
} else if(type[u] == 1){ // LEFT: val >= from, val <= R[u]
for(int v = from; v <= r[u]; v++) res = (res + g(u, v)) % mod;
}else{ // RIGHT: val <= from, val >= L[u]
for(int v = l[u]; v <= from; v++) res = (res + g(u, v)) % mod;
}
return dp[u][from] = res;
}
int g(int u, int x){
if(f[u][x] != -1) return f[u][x];
int res = 1;
for(int v: adj[u]) res = (res * solve(v, x)) % mod;
return f[u][x] = res;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
for(int i = 1; i <= n; i++){
string s1, s2; cin >> s1 >> s2;
if(isdigit(s1[0]) && isdigit(s2[0])){
type[i] = 0; // ROOT
l[i] = stoi(s1);
r[i] = stoi(s2);
}else if(!isdigit(s1[0])){
type[i] = 1; // LEFT (parent is s1)
r[i] = stoi(s2);
adj[s1[0] - 'a' + 1].push_back(i);
}else{
type[i] = 2; // RIGHT (parent is s2)
l[i] = stoi(s1);
adj[s2[0] - 'a' + 1].push_back(i);
}
}
memset(dp, -1, sizeof(dp));
memset(f, -1, sizeof(f));
int ans = 1;
for(int i = 1; i <= n; i++){
if(type[i] == 0) ans = ans * solve(i, 0) % mod;
}
cout << ans;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<int> basis;
for(int i = 0; i < n; i++){
int x; cin >> x;
for(int j = 0; j < basis.size(); j++) x = min(x, x ^ basis[j]);
if(x) basis.push_back(x);
for(auto c: basis) cout << c << " ";
cout << "\n";
}
cout << (1ll << basis.size()) - n;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5;
int a[maxn], b[maxn], d[maxn];
int mnl[maxn], mnr[maxn];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
d[1] = 0;
for(int i = 1; i <= n; i++) d[i + 1] = d[i] + a[i];
stack<int> st;
b[0] = 0;
for(int i = 1; i <= n; i++){
while(!st.empty() && b[st.top()] >= b[i]) st.pop();
mnl[i] = (st.empty() ? 0 : st.top());
st.push(i);
}
while(!st.empty()) st.pop();
b[n + 1] = 0;
for(int i = n; i >= 1; i--){
while(!st.empty() && b[st.top()] > b[i]) st.pop();
mnr[i] = (st.empty() ? n + 1 : st.top());
st.push(i);
}
vector<array<int, 3>> range;
for(int i = 1; i <= n; i++) range.push_back({mnl[i], mnr[i], b[i] - max(b[mnl[i]], b[mnr[i]])});
while(m--){
int s, t, u; cin >> s >> t >> u;
bool ok = true;
for(int i = s; i < t; i++){
if(a[i] > u){
ok = false;
break;
}
}
if(!ok){
cout << -1 << "\n";
continue;
}
long res = 0;
for(auto [l, r, w]: range){
int lbound = max(s, l), rbound = min(t, r);
if(lbound < rbound){
int dist = d[rbound] - d[lbound];
if(l < s) res += dist * w;
else res += max(dist - u, 0ll) * w;
}
}
cout << res << "\n";
}
}
19 joker/star trek
20 misspelling/fish 3
21 reconstruction project/long mansion
22 bulldozer/circle selection
23 treatment project/candies
25 coin arrangemnet/port facilities
26 homework/fire
27 catexercise/rmi colors
28relaymarathon/equalmex
29triangle/fibo...
30 catordog/bubble sort2
31 collapse/council
01 arcade/aesthetic
02 grapevine/towers
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, q; cin >> n >> q;
vector<int> s(n + 1), pre(n + 1), nxt(n + 1);
for(int i = 1; i <= n; i++) cin >> s[i];
stack<int> st;
for(int i = 1; i <= n; i++){
while(!st.empty() && s[st.top()] < s[i]) st.pop();
pre[i] = (st.empty() ? -2e9 : st.top());
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = n; i >= 1; i--){
while(!st.empty() && s[st.top()] <= s[i]) st.pop();
nxt[i] = (st.empty() ? 2e9 : st.top());
st.push(i);
}
//pre[i]:vị trí j < i gần nhất mà s[j] >= s[i]
//nxt[i] vị trí j > i gần nhất mà s[j] > s[i]
/**
đoạn chiếm của s[i] tại thời điểm t
//phải thuộc khoảng [i, i + t];
//phải < nxt[i] (là thuộc) [i, min(nxt[i - 1], i + t)];
//bị pre[i] lan sang nên chiếm được k > pre[i] + t
while(q--){
int t, l, r; cin >> t >> l >> r;
int res = 0;
for(int i = 1; i <= n; i++){
int lbound = max({i, pre[i] + t + 1, l}), rbound = min({nxt[i] - 1, i + t, r});
res += s[i] * max(0ll, rbound - lbound + 1);
}
cout << res << "\n";
}
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e5 + 5;
int adj[maxn][2], d[maxn], up[maxn][20], n;
ll val[maxn], sz[maxn], tot[maxn], h;
void dfs1(int u, int p){
up[u][0] = p;
for(int i = 1; i <= 19; i++) up[u][i] = up[up[u][i - 1]][i - 1];
sz[u] = (u <= n);
if(u <= n) return;
for(int i: {0, 1}){
int v = adj[u][i];
d[v] = d[u] + 1;
dfs1(v, u);
sz[u] += sz[v];
}
}
void dfs2(int u){
if(u <= n) return;
int c1 = adj[u][0], c2 = adj[u][1];
tot[c1] = tot[u] + sz[c2] * val[u] * h;
tot[c2] = tot[u] + sz[c1] * val[u] * h;
dfs2(c1);
dfs2(c2);
}
int acl(int u, int v){
if(d[u] < d[v]) swap(u, v);
for(int i = 19; i >= 0; i--){
if(d[u] - (1 << i) >= d[v]) u = up[u][i];
}
if(u == v) return u;
for(int i = 19; i >= 0; i--){
if(up[u][i] != up[v][i]){
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
int getc(int u, int lca){
if(u == lca) return -1;
for(int i = 19; i >= 0; i--){
if(d[u] - (1 << i) > d[lca]) u = up[u][i];
}
return u;
}
int get_highest_block(int u, ll W){
int cur = u;
for(int i = 19; i >= 0; i--){
if(val[up[cur][i]] > W) cur = up[cur][i];
}
return cur;
}
pair<ll, ll> evaluate(ll W, int u, int v){
if (W == -1) return {0, 0};
int cu = get_highest_block(u, W);
int cv = get_highest_block(v, W);
if(cu == cv) return {n - sz[cu], tot[cu]};
else{
int lca = acl(u, v);
return {n - sz[cu] - sz[cv], tot[lca] + tot[cu] - tot[getc(u, lca)] + tot[cv] - tot[getc(v, lca)]};
}
}
vector<ll> cmp;
void init(const vector<int> &a, const vector<int> &b, const vector<int> &c, int hanh){
n = a.size() + 1;
h = hanh;
vector<array<int, 3>> edge(n - 1);
for(int i = 0; i < n - 1; i++){
edge[i] = {c[i], a[i] + 1, b[i] + 1};
cmp.push_back(c[i]);
}
sort(cmp.begin(), cmp.end());
cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
sort(edge.rbegin(), edge.rend());
vector<int> p(2 * n + 1);
for(int i = 1; i <= 2 * n; i++) p[i] = i;
function<int(int)> find = [&](int u){
return u == p[u] ? u : p[u] = find(p[u]);
};
int cnt = n;
for(int i = 1; i <= n; i++) val[i] = 2e18;
for(auto [w, u, v]: edge){
u = find(u), v = find(v);
p[u] = p[v] = ++cnt;
adj[cnt][0] = u;
adj[cnt][1] = v;
val[cnt] = w;
}
dfs1(cnt, 0);
dfs2(cnt);
}
int query(int u, int v, ll c){
int l = 0, r = cmp.size() - 1, res = -1;
pair<ll, ll> best = {0, 0};
u++, v++;
while(l <= r){
int mid = (l + r) / 2;
auto info = evaluate(cmp[mid], u, v);
if(info.second <= c){
res = mid;
best = info;
l = mid + 1;
}else r = mid - 1;
}
ll ans = best.first, rem = c - best.second;
if(res + 1 < cmp.size()){
long long diff = evaluate(cmp[res + 1], u, v).first - best.first;
if(diff > 0) ans += min(diff, rem / (cmp[res + 1] * h)
