In this HackerEarth Spartans: Leonidas Vs Xerxes problem solution The battle of Thermopylae is between the Persians and Greeks during the Persian invasion. The Greek force is very small but determined to make a stand against the huge Persian army.
All of Greece is in fear, knowing that the army of the Persian king Xerxes has begun its invasion of Greece. Already the Thessalians had gone over to the Persian side, but some Greek cities has come together and forgotten their usual rivalries, determining to stop the Persian invasion. These cities agreed that Sparta would lead the Greek army, as its reputation in war was unmatched by any other Greek state.
The Spartans has chosen to defend a narrow pass,between the mountains of central Greece and the sea, called Thermopylae. Greek force now waiting, made up of only 300 Spartans under their king, Leonidas.
King Xerxes has huge Persian army of 'N' soldiers.They are standing in straight line and each ith soldiers has power Pi . King Xerxes knows that collaboration between adjacent soldiers is more,So Xerxes want to send longest continuous chain of his soldiers among 'N' soldiers such that their power is strictly increasing.
As King Xerxes knows black magic,He can increase or decrease the power of ith soldier.You are the advisor of King Xerxes,He asked you to tell the length of longest continuous increasing chain of soldiers of current army.
At any time, King Xerxes will do two operations :
- 1 x y : Increase the power of xth soldier by 'y' - (if negative, it means decrease.)
- 0 x y : Ask you the length of longest continuous increasing chain of soldiers in range [x , y] inclusive
HackerEarth Spartans : Leonidas Vs Xerxes problem solution.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define em push
#define X first
#define Y second
#define all(v) v.begin(),v.end()
#define uniq(v) sort(all(v));v.erase(unique(all(v)),v.end())
#define _ ios::sync_with_stdio(false);cin.tie(0);
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define endl '\n'
#define MAX 100010
#define MOD 1000000007
namespace segmentTree
{
LL input[MAX];
struct data
{
LL ans,Lis,Ris,L,R,Lm,Rm;
};
data tree[3*MAX];
data combine_data(data left,data right)
{
data res;
res.ans = max(left.ans,right.ans);
if(left.Rm < right.Lm)
res.ans = max(res.ans,left.Ris + right.Lis);
res.L = left.L; res.R = right.R;
res.Lm = left.Lm; res.Rm = right.Rm;
res.Lis = left.Lis; res.Ris = right.Ris;
if(left.Lis == (left.R - left.L +1) && left.Rm < right.Lm)
res.Lis += right.Lis;
if(right.Ris == (right.R - right.L +1) && left.Rm < right.Lm)
res.Ris += left.Ris;
return res;
}
data make_data(int val,int b)
{
data res;
res.ans = res.Lis = res.Ris = 1;
res.Lm = res.Rm = val;
res.L = res.R = b;
return res;
}
void init_tree(int node,int b,int e)
{
if(b==e) // leaf node
{
tree[node] = make_data(input[b],b);
return ;
}
int mid = (b+e)/2;
init_tree(2*node,b,mid);
init_tree(2*node+1,mid+1,e);
tree[node] = combine_data(tree[2*node],tree[2*node+1]);
}
void update(int node,int b,int e,int index,int newval)
{
if(b==e)
{
tree[node].Lm += newval;
tree[node].Rm += newval;
return;
}
int mid = (b+e)/2;
if(index<=mid)
update(2*node,b,mid,index,newval);
else
update(2*node+1,mid+1,e,index,newval);
tree[node] = combine_data(tree[2*node],tree[2*node+1]);
}
data query(int node,int b,int e,int i,int j)
{
if(b >= i && e <= j)//in range
return tree[node];
int mid = (b+e)/2;
if(j<=mid)
return query(2*node,b,mid,i,j);
else if(i>mid)
return query(2*node+1,mid+1,e,i,j);
data p1 = query(2*node,b,mid,i,j);
data p2 = query(2*node+1,mid+1,e,i,j);
return combine_data(p1,p2);
}
}
using namespace segmentTree;
int main()
{_
int t,n,q,a,b,type;
cin>>t;
while(t--)
{
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>input[i];
init_tree(1,1,n);
while(q--){
cin>>type>>a>>b;
if(type == 0){
data ret = query(1,1,n,a,b);
cout<<ret.ans<<endl;
}
else
update(1,1,n,a,b);
}
}
return 0;
}Second solution
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<unordered_map>
#include<unordered_set>
//#include<quadmath.h>
using namespace std;
struct st{
long long int left_val;
long long int right_val;
int left_count;
int right_count;
int maxt;
int range;
void init(){
left_val = right_val = left_count = right_count = 0;
maxt = 0;
}
st(){
init();
}
};
#define MAX 100002
st seg[MAX * 4];
int n;
int q;
namespace test{
void end_test(){
int val;
if (cin >> val){
exit(1);
}
}
void range_test(int t,int l,int r){
if (t < l || r < t){
exit(1);
}
}
}
long long int p[MAX];
st emp;
st merge(st a, st b){
if (a.maxt == -1){
return b;
}
if (b.maxt == -1){
return a;
}
st nex;
nex.init();
nex.maxt = max(a.maxt, b.maxt);
if (a.right_val < b.left_val){
nex.maxt = max(nex.maxt, a.right_count + b.left_count);
}
nex.left_val = a.left_val;
nex.right_val = b.right_val;
nex.range = a.range + b.range;
if (a.left_count ==a.range){
if (a.right_val < b.left_val){
nex.left_count = a.range + b.left_count;
}
else{
nex.left_count = a.range;
}
}
else{
nex.left_count = a.left_count;
}
if (b.right_count == b.range){
if (a.right_val < b.left_val){
nex.right_count = a.right_count + b.range;
}
else{
nex.right_count = b.range;
}
}
else{
nex.right_count = b.right_count;
}
return nex;
}
inline void init(int b, int l, int r){
seg[b].range = r - l;
if (l + 1 == r){
seg[b].left_val = seg[b].right_val = p[l];
seg[b].left_count = seg[b].right_count = 1;
seg[b].maxt = 1;
return;
}
init(b * 2 + 1, l, (l + r) >> 1);
init(b * 2 + 2, (l + r) >> 1, r);
seg[b] = merge(seg[b * 2 + 1], seg[b * 2 + 2]);
}
inline void add(int b, int l, int r, int ll,long long int x){
if (l <= ll&&ll < r){
if (l + 1 == r){
seg[b].init();
seg[b].left_count = seg[b].right_count = 1;
seg[b].left_val = seg[b].right_val = x;
seg[b].range = r - l;
seg[b].maxt = 1;
return;
}
add(b * 2 + 1, l, (l + r) >> 1, ll, x);
add(b * 2 + 2, (l + r) >> 1, r, ll, x);
seg[b] = merge(seg[b * 2 + 1], seg[b * 2 + 2]);
}
return;
}
inline st qq(int b, int l, int r, int ll, int rr){
if (rr <= l || r <= ll){
return emp;
}
if (ll <= l&&r <= rr){
return seg[b];
}
st rrr = qq(b * 2 + 1, l, (l + r) >> 1, ll, rr);
rrr = merge(rrr, qq(b * 2 + 2, (l + r) >> 1, r, ll, rr));
return rrr;
}
int main(){
emp.init();
emp.maxt = -1;
int t;
scanf("%d", &t);
test::range_test(t, 1, 10);
while (t--){
int n, q;
scanf("%d%d", &n, &q);
test::range_test(n, 1, 100000);
test::range_test(q, 1, 100000);
for (int i = 0; i < n; i++){
scanf("%lld", &p[i]);
test::range_test(p[i], 1, 1000000000);
}
init(0, 0, n);
while (q--){
int ty;
scanf("%d", &ty);
if (ty == 1){
int x;
long long int y;
scanf("%d%lld", &x, &y);
test::range_test(x, 1, n);
test::range_test(abs(y), 0, 1000000000);
x--;
p[x]+=y;
add(0, 0, n, x, p[x]);
continue;
}
else{
int x, y;
scanf("%d%d", &x, &y);
if (x > y){
exit(1);
}
test::range_test(x, 1, n);
test::range_test(y, 1, n);
x--;
y--;
st ans = qq(0, 0, n, x, y + 1);
printf("%d\n", ans.maxt);
}
}
}
test::end_test();
return 0;
}
0 Comments