Skip to main content

Posts

FREQUENT

FREQUENT                                                         segment tree #include <iostream> #include <algorithm> #include <stdio.h> #define sf(i) scanf("%d", &i) #define pf(i) printf("%d\n", i) #define pii pair<int, int> #define mp make_pair #define f first // value #define s second //frequency #define FOR(a, b) for(int i = a; i < b; i++) using namespace std; const int N = 100001; struct node {     pii m;     pii l;     pii r; }; int n, q; int arr[N]; node seg[4 * N]; node combine(node &a, node &b) {     node res;     if(a.l.f == b.r.f) //if all the elements are same     {         res.l.f = res.r.f = res.m.f = a.l.f;         res.l.s ...

D-QUERY

                                              D-Query                                            segment tree + offline method #include <iostream> #include <algorithm> #include <stdio.h> #include <map> #define sf(i) scanf("%d", &i) #define pf(i) printf("%d\n", i) using namespace std; const int N = 30001; const int Q = 200001; struct node {     int l, r;     int pos,     int val; }; int n, q; node arr[N + Q]; int result[Q]; int seg[4 * N]; map<int, int> last_pos; node makenode(int l, int r, int pos, int val) {     node temp;     temp.l = l;     temp.r = r;     temp.pos = pos;     te...

GSS1

                                                     GSS1                                                                 segment tree Problem Link #include <iostream> #include <stdio.h> using namespace std; struct node {     long bestSum, leftSum, rightSum, totalSum; }; int n; long t; node seg[200003]; long arr[50003]; node combine(node &lc, node &rc) {     node temp;     temp.totalSum = lc.totalSum + rc.totalSum;     temp.leftSum = max(lc.leftSum, lc.totalSum + rc.leftSum);     temp.rightSum = max(rc.rightSum, rc.totalSum + lc.rightSum);     temp.bestSum = max(lc.right...

Sereja and Brackets

                                Sereja and Brackets                                   segment tree Problem Link #include <iostream> #include <cmath> #include <cstring> using namespace std; string s; struct node {     long int len; //max length of matched brackets     int tn, tp; // tp = total number of '(' brackets                 //tn = total number of ')' brackets }; node func(node a, node b) {     node temp;     int len = min(a.tp, b.tn);     temp.len = a.len + b.len + 2 * len;     temp.tp = a.tp + b.tp - len;     temp.tn = a.tn + b.tn - len;     return temp; } void buildTree(node seg[], int l, int r, int index) { ...

Chef and Sub Array

                      Chef and Sub Array Problem Link #include <iostream> #include <stdio.h> #define sf(i) scanf("%d", &i) #define pf(i) printf("%d\n", i) using namespace std; int n, k, p; int a[100005], b[300005]; int sum[300005], tree[700005]; string s; void buildTree(int index, int s, int e) {     if(s == e)     {         tree[index] = sum[s];     }     else     {         int mid = (s + e) / 2;         buildTree(2 * index + 1, s, mid);         buildTree(2 * index + 2, mid + 1, e);         tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);     } } int query(int index, int s, int e, int qs, int qe) {     if(qs > e || qe < s)         return 0;...

Book of Evil

                                        Book of Evil Problem Link #include <iostream> #include <vector> #include <cstring> #include <stdio.h> #define sf(i) scanf("%d", &i) #define pf(i) printf("%d\n", i) #define pb push_back using namespace std; const int N = 1e5 + 1; int h[N]; bool mark[N],ans[N]; vector<int> g[N]; int n, m, d, D, R; void dfs(int s, int p) {     h[s] = h[p] + 1;     ans[s] &= (h[s] <= d);     if(mark[s] && h[s] > D)     {         D = h[s], R = s;     }     for(int i = 0; i < g[s].size(); i++)     {         int v = g[s][i];         if(v == p)             continue;         d...

Chloe and pleasant prizes

                            Chloe and pleasant prizes Problem Link #include <iostream> #include <vector> #define pb push_back using namespace std; typedef long long int li; const li N = 2 * 1e5 + 5; const li inf = 1LL<<60; vector<li> g[N];  li p[N]; li sum[N]; li dp[N]; li n, u, v; li ans = -inf; void dfs(int s, int t) {          dp[s] = -inf;     sum[s] = p[s];     for(int i = 0; i < g[s].size(); i++)     {         int v = g[s][i];         if(v == t)            continue;         dfs(v, s);         sum[s] += sum[v];         if(dp[s] > -inf)ans=max(ans,dp[s]+dp[v]);         dp[s]=max(dp[s],dp[v]);     } ...