link :https://www.hackerrank.com/skdece39
1]
IN C
Mr. X and His Shots
#include <stdio.h>
#include <stdlib.h>
void sort_a(int*a,int size);
void merge(int*a,int*left,int*right,int left_size, int right_size);
int get_i(int*a,int num,int size);
int med(int*a,int size);
int h[100000],t[100000];
int main(){
int N,M,x,y,tt,i;
long long ans=0;
scanf("%d%d",&N,&M);
for(i=0;i<N;i++)
scanf("%d%d",h+i,t+i);
sort_a(h,N);
sort_a(t,N);
for(i=0;i<M;i++){
scanf("%d%d",&x,&y);
tt=0;
tt+=get_i(t,x,N);
tt+=N-get_i(h,y+1,N);
tt=N-tt;
ans+=tt;
}
printf("%lld",ans);
return 0;
}
void sort_a(int*a,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left,*right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
sort_a(left,m);
sort_a(right,size-m);
merge(a,left,right,m,size-m);
free(left);
free(right);
return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right[j];
j++;
} else if (j == right_size) {
a[i+j] = left[i];
i++;
} else if (left[i] <= right[j]) {
a[i+j] = left[i];
i++;
} else {
a[i+j] = right[j];
j++;
}
}
return;
}
int get_i(int*a,int num,int size){
if(size==0)
return 0;
if(num>med(a,size))
return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
else
return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
return a[(size-1)>>1];
}
2]
IN C
Jim and the Skyscrapers
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct {
int value;
int count;
} stack[300001];
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n, i, num, end=0;
long long result = 0;
stack[0].value = 1000001;
scanf("%d", &n);
for (i=0; i<n; i++) {
scanf("%d", &num);
while (stack[end].value < num) {
result += (long long)stack[end].count * (stack[end].count-1);
--end;
}
if (stack[end].value == num) {
++stack[end].count;
} else {
++end;
stack[end].value = num;
stack[end].count = 1;
}
}
while (end > 0) {
result += (long long)stack[end].count * (stack[end].count-1);
--end;
}
printf("%lld", result);
return 0;
}
3}
Ticket to Ride
#include <bits/stdc++.h>
using namespace std;
struct segtree
{
int n;
vector<long long> seg;
vector<long long> lazy;
void init(int n)
{
this->n=n;
int lg=0;
while((1<<lg)<n)
lg++;
lg++;
seg.resize(1<<lg);
lazy.resize(1<<lg);
fill(seg.begin(), seg.end(), 0LL);
fill(lazy.begin(), lazy.end(), 0LL);
}
void push_down(int idx)
{
if(lazy[idx])
{
seg[idx*2]+=lazy[idx];
lazy[idx*2]+=lazy[idx];
seg[idx*2+1]+=lazy[idx];
lazy[idx*2+1]+=lazy[idx];
lazy[idx]=0;
}
}
void tree_update(int idx, int begin, int end, int l, int r, long long v)
{
if(r<begin || end<l)
return;
if(l<=begin && end<=r)
{
seg[idx]+=v;
lazy[idx]+=v;
}
else
{
push_down(idx);
int mid=(begin+end)/2;
tree_update(idx*2, begin, mid, l, r, v);
tree_update(idx*2+1, mid+1, end, l, r, v);
seg[idx]=max(seg[idx*2], seg[idx*2+1]);
}
}
void update(int l, int r, long long v)
{
tree_update(1, 1, n, l, r, v);
}
long long tree_query(int idx, int begin, int end, int l, int r)
{
if(r<begin || end<l)
return -0x3f3f3f3f3f3f3f3fLL;
if(l<=begin && end<=r)
return seg[idx];
push_down(idx);
int mid=(begin+end)/2;
return max(tree_query(idx*2, begin, mid, l, r),
tree_query(idx*2+1, mid+1, end, l, r));
}
long long query(int l, int r)
{
if(l>r)
return -0x3f3f3f3f3f3f3f3fLL;
return tree_query(1, 1, n, l, r);
}
};
struct edge
{
int v, c;
bool operator== (const edge& other) const
{
return v==other.v && c==other.c;
}
};
int N, M;
vector<edge> adj[200001];
vector<edge> path[200001];
int sz[200001];
int in[200001];
int out[200001];
int now;
bool visited[200001];
long long base[200001];
bool on_stack[200001];
void dfs_sz(int u, int p)
{
sz[u]=1;
for(auto& it: adj[u])
{
int v=it.v;
if(it.v==p)
continue;
dfs_sz(v, u);
sz[u]+=sz[v];
}
}
void init_dfs(int u, int p)
{
visited[u]=false;
in[u]=++now;
for(auto& it: adj[u]) if(it.v!=p)
init_dfs(it.v, u);
out[u]=now;
}
long long dfs(int u, int p, long long cost, int sroot, segtree& tree)
{
visited[u]=true;
on_stack[u]=true;
base[u]=cost;
static vector<edge> p1;
vector<edge> p2;
p1.clear();
for(auto& it: path[u])
{
int v=it.v, c=it.c;
if(on_stack[v])
base[u]+=c;
if(in[sroot]<=in[v] && in[v]<=out[sroot])
p1.push_back(it);
else if(visited[v])
p2.push_back(it);
}
tree.update(in[u], in[u], base[u]);
path[u].swap(p1);
for(auto& it: p2)
tree.update(in[it.v], out[it.v], it.c);
long long ret=base[u]+tree.query(1, in[sroot]-1);
for(auto& it: adj[u]) if(it.v!=p)
{
int v=it.v, c=it.c;
ret=max(ret, dfs(v, u, base[u]-c, sroot, tree));
}
for(auto& it: p2)
tree.update(in[it.v], out[it.v], -it.c);
on_stack[u]=false;
return ret;
}
segtree tree;
long long solve_tree(int u, int n)
{
tree.init(n);
now=0;
init_dfs(u, u);
base[u]=0;
for(auto& it: path[u]) if(it.v==u)
base[u]+=it.c;
on_stack[u]=true;
long long ret=base[u];
for(auto& it: adj[u])
{
int v=it.v, c=it.c;
ret=max(ret, base[u]+dfs(v, u, -c, v, tree));
}
on_stack[u]=false;
return ret;
}
long long dac(int u)
{
dfs_sz(u, u);
while(1)
{
int v=-1;
for(auto& it: adj[u]) if(v==-1 || sz[it.v]>sz[v])
v=it.v;
if(v==-1 || sz[v]*2<=sz[u])
break;
sz[u]-=sz[v];
sz[v]+=sz[u];
u=v;
}
long long ret=solve_tree(u, sz[u]);
for(auto& it: adj[u])
{
int v=it.v, c=it.c;
adj[v].erase(find(adj[v].begin(), adj[v].end(), (edge){u, c}));
ret=max(ret, dac(v));
}
return ret;
}
int main()
{
scanf("%d", &N);
int a, b, c;
for(int i=0; i<N-1; i++)
{
scanf("%d%d%d", &a, &b, &c);
adj[a].push_back((edge){b, c});
adj[b].push_back((edge){a, c});
}
scanf("%d", &M);
for(int i=0; i<M; i++)
{
scanf("%d%d%d", &a, &b, &c);
path[a].push_back((edge){b, c});
if(a!=b)
path[b].push_back((edge){a, c});
}
printf("%lld\n", dac(1));
return 0;
}
