1

1.
2. #include <bits/stdc++.h>
3. #define ll long long
4. #define f(i,n) for(int i=0;i<n;i++)
5. #define vi vector<int>
6. #define vvi vector<vector<int>>
7. #define pb push_back
8. using namespace std;
9.
10. void solve(int k,int l, int r, vi &v,int a[]){
11. if(l>r){
12. return ;
13. }
14.
15.
16. if(l==r){
17. v[l]=k;
18. return ;
19. }
20.
21.
22. int maxi=-1;
23. int ind=-1;
24. for(int i=l;i<=r;i++){
25. if(maxi < a[i]){
26. maxi= a[i];
27. ind= i;
28. }
29. }
30. v[ind]=k;
31. solve(k+1,l,ind-1,v,a);
32. solve(k+1,ind+1,r,v,a);
33.
34. return ;
35. }
36.
37. int main(){
38. int t; cin>>t;
39. while(t--){
40. int n; cin>>n;
41. int a[n];
42. for(int i=0;i<n;i++){
43. cin>>a[i];
44. }
 45. vi v(n,-1);
46. solve(0,0,n-1,v,a);
47.
48. for(int i=0;i<n;i++){
49. cout<<v[i]<<" ";
50. }
51. cout<<endl;
52. }
53. return 0;
54. }
https://codeforces.com/problemset/problem/1490/D

2
1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. int t, n;
5. string s;
6.
7. int get_ans(int l, int r, char c){
8. if(l == r) return s[l] != c;
9. int tot1 = 0, tot2 = 0, mid = (l + r) >> 1;
10. for(int i = l; i <= mid; i++){
11. if(s[i] != c) tot1++;
12. }
13. for(int i = mid + 1; i <= r; i++){
14. if(s[i] != c) tot2++;
15. }
16. tot1 += get_ans(mid + 1, r, c + 1);
17. tot2 += get_ans(l, mid, c + 1);
18. return min(tot1, tot2);
19. }
20.
21. int main(){
22. cin >> t;
23. while(t--){
24. cin >> n;
25. cin >> s;
26. s = '@' + s;
27. int x = get_ans(1, n, 'a');
28. cout << x << endl;
29. }
30. return 0;
31. }
https://codeforces.com/problemset/problem/1385/D

3
1. #include<bits/stdc++.h>
2. using namespace std;
3. #define ll long long int
4. ll ar[200003];
5. ll dp1[200003];
6. ll dp2[200003];
7. ll n;
8. ll ok(ll i)
9. {
10. if(i>=n) return 0;
11. if(dp1[i]!=-1)
12. return dp1[i];
13. ll op=0;
14. op=max(op,ar[i+1]-ar[i]+ok(i+2));
15. return dp1[i]=op;
16. }
17. ll ok2(ll i)
18. {
19. if(i>=n)
20. return 0;
21. if(dp2[i]!=-1)
22. return dp2[i];
23. ll op=0;
24. op=max(op,ar[i]-ar[i+1]+ok2(i+2));
25. return dp2[i]=op;
26. }
27. int main()
28. {
29. ll tc;
30. cin>>tc;
31. while(tc--)
32. {
33. cin>>n;
34. memset(dp1,-1,sizeof(dp1));
35. memset(dp2,-1,sizeof(dp2));
36. ll s=0;
37. for(int i=1;i<=n;i++){
 38. cin>>ar[i];
39. if(i%2)
40. s+=ar[i];
41. }
42. ll mx=0;
43. for(int i=1;i<=n;i++)
44. {
45. if(i%2)
46. mx=max(mx,s+ok(i));
47. else
48. mx=max(mx,s+ok2(i));
49. }
50. cout<<mx<<endl;
51. }
52. }

https://codeforces.com/problemset/problem/
1373/D

4
1. #include<bits/stdc++.h>
2. using namespace std;
3. #define ll long long int
4.
5.
6. int ans=0;
7. vector<int> a;
8.
9. void Call(int l1,int r1,int l2,int r2){
10. int mxL=0;
11. for(int i=l1;i<=r1;i++){
12. mxL=max(mxL,a[i]);
13. }
14. int mnR=INT_MAX;
15. for(int i=l2;i<=r2;i++){
16. mnR=min(mnR,a[i]);
17. }
18. if(mxL>mnR){
19.
20. int R=l2;
21. for(int i=l1;i<=r1;i++){
22. swap(a[i],a[R]);
23. R++;
24. }
25. ans++;
26. }
27. if(l1==r1)return;
28. int mid1=(l1+r1)/2;
29. int mid2=(l2+r2)/2;
 30.
31. Call(l1,mid1,mid1+1,r1);
32. Call(l2,mid2,mid2+1,r2);
33. }
34.
35. int main(){
36.
37. int t; cin>>t;
38. while(t--){
39. int n; cin>>n;
40. a.resize(n+1);
41.
42. for(int i=1;i<=n;i++){
43. cin>>a[i];
44. }
45.
46. ans=0;
47. if(is_sorted(a.begin()+1,a.begin()+n+1)){
48. cout<<0<<endl;
49. continue;
50. }
51.
52. int mid=(n+1)/2;
53. Call(1,mid,mid+1,n);
54.
55. if(is_sorted(a.begin()+1,a.begin()+n+1)){
56. cout<<ans<<endl;
57. }
58. else{
59. cout<<-1<<endl;
60. }
61. }
62. return 0;
63. }

https://codeforces.com/problemset/problem/
1741/D

5
1. #include <bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. #define float long double
5. const int mod = 1e9 + 7;
6. const int inf = 1e18;
7.
8. const int N=200005;
9. int n;
10. int dp[N][2];
 11. vector<int>adj[N];
12. int a[N][2];
13.
14. void dfs(int i,int par)
15. {
16. dp[i][0]=dp[i][1]=0;
17. for(auto x:adj[i])
18. {
19. if(x!=par)
20. {
21. dfs(x,i);
22. dp[i][0]+=max(dp[x][0]+abs(a[i][0]-a[x][0]),dp[x]
[1]+abs(a[i][0]-a[x][1]));
23. dp[i][1]+=max(dp[x][1]+abs(a[i][1]-a[x][1]),dp[x]
[0]+abs(a[i][1]-a[x][0]));
24. }
25. }
26. }
27. void solve()
28. {
29. cin>>n;
30.
31. for(int i=1;i<=n;i++)
32. cin>>a[i][0]>>a[i][1];
33.
34. fill(adj + 1, adj + n + 1, vector<int>());
35.
36. for(int i=1;i<n;i++)
37. {
38. int u,v;
39. cin>>u>>v;
40. adj[u].push_back(v);
41. adj[v].push_back(u);
42. }
43.
44. dfs(1,0);
45. cout<<max(dp[1][0],dp[1][1])<<endl;
46. }
47. int32_t main()
48. {
49. std::ios::sync_with_stdio(false);
50. std::cin.tie(nullptr);
51. int t = 1;
52. cin >> t;
53. while (t--)
54. {
55. solve();
56. }
57. return 0;
58. }

https://codeforces.com/problemset/problem/
1528/A
6
1. #include<bits/stdc++.h>
2. #define speed ios_base::sync_with_stdio(false); cin.tie(NULL);
cout.tie(NULL);
3. #define ff first
4. #define ss second
5. #define ll int64_t
6. using namespace std;
7.
8. void sort_one(string &s, int l, int r) {
9. if ((r - l) & 1) return;
10.
11. int m = (l + r) / 2;
12. sort_one(s, l, m);
13. sort_one(s, m, r);
14.
15. int f = 0;
16.
17. for (int i = 0; i < m - l; i++) {
18. if (s[l + i] != s[m + i]) {
19. f = (s[l + i] > s[m + i]);
20. break;
21. }
22. }
23.
24. if (f) {
25. for (int i = 0; i < m - l; i++) swap(s[l + i], s[m + i]);
26. }
27. }
28.
29. void solve()
30. {
31. string s, t;
32. cin >> s >> t;
33. int n = s.size();
34. sort_one(s, 0, n);
35. sort_one(t, 0, n);
36.
37. if (s == t) cout << "YES" << endl;
38. else cout << "NO" << endl;
39. }
40.
41. int main()
42. {
43. speed
44. int T; T = 1;
45. while (T--) {
46. solve();
47. }
48.
49. return 0;
50. }

https://codeforces.com/problemset/problem/559/B
7
1. #include<bits/stdc++.h>
2.
3. using namespace std;
4.
5. vector<int> p = {4, 8, 15, 16, 23, 42};
6. int ans[4];
7.
8. int main()
9. {
10. for(int i = 0; i < 4; i++)
11. {
12. cout << "? " << i + 1 << " " << i + 2 << endl;
13. cout.flush();
14. cin >> ans[i];
15. }
16. do
17. {
18. bool good = true;
19. for(int i = 0; i < 4; i++)
20. good &= (p[i] * p[i + 1] == ans[i]);
21. if(good) break;
22. }
23. while(next_permutation(p.begin(), p.end()));
24. cout << "!";
25. for(int i = 0; i < 6; i++)
26. cout << " " << p[i];
27. cout << endl;
28. cout.flush();
29. return 0;
30. }

https://codeforces.com/problemset/problem/
1167/B

8
1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. int main() {
5. int t;
6. cin >> t;
7.
8. while (t--) {
 9. long long n, ans = 0;
10. cin >> n;
11. vector<int> vl(n), vll(n + 1);
12.
13. for (int i = 0; i < n; i++)
14. cin >> vl[i];
15.
16. for (int i = n - 1; i >= 0; i--) {
17. for (int x = vl[i]; x > 0; x -= x & -x)
18. ans += vll[x];
19.
20. for (int x = vl[i]; x <= n; x += x & -x)
21. vll[x]++;
22. }
23.
24. cout << ans << '\n';
25. }
26.
27. return 0;
28. }

https://codeforces.com/problemset/problem/
1676/H2
9

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define endl "\n"
4. #define con (f ? "YES" : "NO")
5. #define loj(i, j) "Case " << i << ": " << j
6.
7. long long cnt = 0;
8.
9. long long calc(long long n)
10. {
11. if (n % 2)
12. return n * ((n - 1) / 2);
13. return (n / 2) * (n - 1);
14. }
15.
16. long long find(long long a, vector<long long> &par)
17. {
18. if (par[a] == a)
19. return a;
20. return par[a] = find(par[a], par);
21. }
22.
23. void merge(long long a, long long b, vector<long long> &par,
vector<long long> &rk)
24. {
25. a = find(a, par);
26. b = find(b, par);
27.
28. if (rk[a] < rk[b])
29. swap(a, b);
30.
31. cnt = cnt - calc(rk[a]) - calc(rk[b]);
32.
33. rk[a] += rk[b];
34. par[b] = a;
35.
36. cnt +=calc(rk[a]);
37. }
38.
39. struct Tree
40. {
41. long long w, x, y;
42. };
43.
44. int main()
45. {
46. ios_base::sync_with_stdio(false);
47. cin.tie(0), cout.tie(0);
48.
49. long long n, m;
50. cin >> n >> m;
51. vector<long long> par(n), rk(n, 1);
52. iota(par.begin(), par.end(), 0);
53.
54. Tree v[n];
55. for (long long i = 0; i < n - 1; i++)
56. {
57. cin >> v[i].x >> v[i].y >> v[i].w;
58. v[i].x--;
59. v[i].y--;
60. }
61.
62. sort(v, v + n - 1, [](Tree a, Tree b)
63. { return a.w < b.w; });
64.
65. pair<long long, long long> p[m];
66. for (long long i = 0; i < m; i++)
67. {
68. cin >> p[i].first;
69. p[i].second = i;
70. }
71.
72. sort(p, p + m);
73.
74. vector<long long> ans(m);
75.
76. long long j = 0;
77. for (long long i = 0; i < m; i++)
78. {
79. while (j < n - 1 && v[j].w <= p[i].first)
80. {
81. merge(v[j].x, v[j].y, par, rk);
 82. j++;
83. }
84. ans[p[i].second] = cnt;
85. }
86.
87. for (long long i = 0; i < m; i++)
88. cout << ans[i] << " ";
89. }

https://codeforces.com/problemset/problem/
1213/G

10
1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. int t,n,q,a[101000],ans,s,len=0;
5. long long num[2010000];
6.
7.
8. void f(int l,int r,long long sum){
9. if(l>=r)return;
10. int mx=a[r-1],mn=a[l],mid=(mx+mn)/2;
11. num[len++]=sum;
12. if(mx==mn)return;
13. int i=l;long long sum1=0;
14. while(i<r&&a[i]<=mid)sum1+=a[i++];
15. f(l,i,sum1);
16. f(i,r,sum-sum1);
17. return;}
18.
19. int main(){
20. ios_base::sync_with_stdio(false);cin.tie(0);
21. cin>>t;
22. while(t--){
23. long long sum=0;
24. cin>>n>>q;
25. for(int i=0;i<n;i++){
26. cin>>a[i];
27. sum+=a[i];}
28. sort(a,a+n);
29. len=0;
30. f(0,n,sum);
31.
32. sort(num,num+len);
33. while(q--){
34. cin>>s;
35. int it=lower_bound(num,num+len,s)-num;
36. if(0<=it&&it<len&&num[it]==s)cout<<"Yes\n";
 37. else cout<<"No\n";}
38. }
39. return 0;}

https://codeforces.com/problemset/problem/
1461/D

11
1. #include<bits/stdc++.h>
2. using namespace std;
3. int a[5001];
4. int f(int l,int r,int h){
5. if(r<l)return 0;
6. int m=min_element(a+l,a+r+1)-a;
7. return min(r-l+1,f(l,m-1,a[m])+f(m+1,r,a[m])+a[m]-h);
8. }
9. int main(){
10. int n;cin>>n;
11. for(int i=0;i<n;i++)cin>>a[i];
12. cout<<f(0,n-1,0)<<endl;
13. return 0;
14. }

https://codeforces.com/problemset/problem/448/C

12
1. #include<bits/stdc++.h>
2. #define int long long
3. using namespace std;
4. const int N=2e5+5;
5. int t,n;
6. int a[N],f[N][21];
int gcd(int a,int b){
7. if(b==0) return a;
8. else return gcd(b,a%b);
9. }
10. int query(int l,int r){
11. int k=log2(r-l+1);
12. return gcd(f[l][k],f[r-(1<<k)+1][k]);
13. }
14. signed main(){
15. ios::sync_with_stdio(0);
16. cin>>t;
17. while(t--){
 18. cin>>n;
19. for(int i=1;i<=n;i++){
20. cin>>a[i];
21. f[i][0]=abs(a[i]-a[i-1]);
22. }
23. if(n==1){
24. cout<<1<<endl;
25. continue;
26. }
27. for(int j=1;j<=20;j++){
28. for(int i=1;i+(1<<j)-1<=n;i++){
29. f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-
1]);
30. }
31. }
32. int l=1,r=2,ans=0;
33. while(r<=n){
34. while(l<r&&query(l+1,r)<=1) l++;
35. ans=max(ans,r-l+1);
36. r++;
37. }
38. cout<<ans<<endl;
39. }
40. return 0;
41. }

https://codeforces.com/problemset/problem/
1549/D