In this HackerEarth ( Problem F ) Pikachu and Team Rocket problem solution Team Rocket is back with N of their Pokemon to trouble Pikachu. The Team Rocket's Pokemon are numbered from 1 to N and the ith pokemon has health equal to ai.
Pikachu has to battle multiple Pokemon simultaneously. In a single battle, Team Rocket will make Pikachu fight against all the Pokemon in the range [l,r]. Pikachu can defeat a Pokemon if his attack value is at least the Pokemon's health. So, he wants to know the minimum attack he must have to defeat all Pokemon in the range.
However, this time, Team Rocket is stronger than ever. They have designed a technology to modify their Pokemon's health as either of two ways:
- Type 1: They choose some k (1 <= k <= N), and then health changes as ai = ai+1 (k <= i < N) and aN = ak.
- Type 2: They choose some k (1 <= k <= N), and then health changes as ai = ai-1 (1 < i <= K) and a1 = ak.
Note that, all health changes occur simultaneously.
There will be Q events. Each event will be either a battle, or some modification of Pokemon's health by Team Rocket.
For each battle, help Pikachu by finding the minimum attack value he must have to win against all Pokemon in the range.
HackerEarth ( Problem F ) Pikachu and Team Rocket problem solution.
#include<bits/stdc++.h>
using namespace std;
#define N 600005
int a[N],st,en;
struct segTree{
int tree[4*N],x,y,val;
void construct(int low,int high,int pos) {
if(low==high) {
tree[pos]=a[low];
return;
}
int mid=(high+low)/2;
construct(low,mid,2*pos+1);
construct(mid+1,high,2*pos+2);
tree[pos]=max(tree[2*pos+1],tree[2*pos+2]);
}
int query(int low,int high,int pos) {
if(x<=low && y>=high) return tree[pos];
if(x>high||y<low) return 0;
int mid=(high+low)/2;
return max(query(low,mid,2*pos+1),query(mid+1,high,2*pos+2));
}
void update(int low,int high,int pos) {
if(x<low||x>high) return;
if(low==high) {
tree[pos]=val;
return;
}
int mid=(low+high)/2;
update(low,mid,2*pos+1), update(mid+1,high,2*pos+2);
tree[pos]=max(tree[2*pos+1],tree[2*pos+2]);
}
} segtree;
int ft[N];
void upd(int x,int val) {
for(;x<N;x+=(x&-x)) ft[x] += val;
}
int query(int x) {
int ret = 0;
for(;x>0;x-=(x&-x)) ret += ft[x];
return ret;
}
int mk[N];
int get(int orig_pos) {
int low = st, high = en;
while(high-low>1) {
int mid = (low + high)/2;
if(query(mid) >= orig_pos) high = mid;
else low = mid;
}
int new_pos;
if(query(low) == orig_pos) new_pos = low;
else new_pos = high;
return new_pos;
}
int main() {
int n,k,type,type2,x,l,r,q;
cin>>n>>q;
int tree_size = q+n+q;
assert(n>=1 and n<=200000);
assert(q>=1 and q<=200000);
st = q+1, en = q+n;
for(int i=1;i<=n;i++) {
cin>>a[i+q];
assert(a[i+q]>=1 and a[i+q]<=1000000000);
upd(i+q,1);
}
segtree.construct(1,tree_size,0);
while(q--) {
cin>>type;
assert(type==1 or type==2);
if(type==2) {
cin>>type2>>x;
assert(type2==1 or type2==2);
assert(x>=1 and x<=n);
int npos = get(x);
upd(npos,-1);
segtree.x = npos, segtree.val = 0;
segtree.update(1,tree_size,0);
if(type2==2) {
--st;
upd(st,1);
a[st] = a[npos];
a[npos] = 0;
segtree.x = st, segtree.val = a[st];
segtree.update(1,tree_size,0);
}
else {
++en;
upd(en,1);
a[en] = a[npos];
a[npos] = 0;
segtree.x = en, segtree.val = a[en];
segtree.update(1,tree_size,0);
}
}
else {
cin>>l>>r;
assert(l>=1 and l<=n);
assert(r>=1 and r<=n);
assert(r>=l);
segtree.x = get(l), segtree.y = get(r);
cout<<segtree.query(1,tree_size,0)<<endl;
}
}
}Second solution
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
TaskD solver = new TaskD();
solver.solve(1, in, out);
out.close();
}
static class TaskD {
public static int n;
public static int q;
public static int front;
public static int back;
public static int[] arr;
public void solve(int testNumber, InputReader in, OutputWriter out) {
n = in.nextInt();
q = in.nextInt();
front = q;
back = n + q - 1;
arr = in.readIntArray(n);
TaskD.SegmentTree root = new TaskD.SegmentTree(0, q + q + n);
while (q-- > 0) {
int type = in.nextInt();
if (type == 1) {
int l = in.nextInt() - 1, r = in.nextInt() - 1;
out.println(root.query(l, r)[0]);
} else {
int t = in.nextInt(), pos = in.nextInt() - 1;
int k = root.unset(pos);
if (t == 2) root.set(--front, k);
else root.set(++back, k);
}
}
}
static class SegmentTree {
public int start;
public int end;
public int count;
public int max;
public TaskD.SegmentTree left;
public TaskD.SegmentTree right;
public SegmentTree(int start, int end) {
this.start = start;
this.end = end;
if (start != end) {
int mid = (start + end) / 2;
left = new TaskD.SegmentTree(start, mid);
right = new TaskD.SegmentTree(mid + 1, end);
this.max = Math.max(left.max, right.max);
this.count = left.count + right.count;
} else if (front <= start && start <= back) {
max = arr[start - q];
count = 1;
} else {
max = -1000000;
count = 0;
}
}
public int[] query(int from, int to) {
if (from == 0 && to == this.count - 1) {
return new int[]{this.max, this.count};
}
if (left.count <= from) {
return right.query(from - left.count, to - left.count);
}
if (left.count > to) {
return left.query(from, to);
}
int want = to - from + 1;
int[] r1 = left.query(from, left.count - 1);
int[] r2 = right.query(0, want - r1[1] - 1);
return new int[]{Math.max(r1[0], r2[0]), r1[1] + r2[1]};
}
public int unset(int index) {
if (this.start == this.end) {
int v = this.max;
this.count = 0;
this.max = -1000000;
return v;
}
int res;
if (left.count > index) {
res = left.unset(index);
} else {
res = right.unset(index - left.count);
}
this.count = left.count + right.count;
this.max = Math.max(left.max, right.max);
return res;
}
public void set(int pos, int val) {
if (start == pos && end == pos) {
this.count = 1;
this.max = val;
return;
}
int mid = (start + end) / 2;
if (pos <= mid) left.set(pos, val);
else right.set(pos, val);
this.count = left.count + right.count;
this.max = Math.max(left.max, right.max);
}
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1 << 16];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int[] readIntArray(int tokens) {
int[] ret = new int[tokens];
for (int i = 0; i < tokens; i++) {
ret[i] = nextInt();
}
return ret;
}
public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;
try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}
if (this.numChars <= 0) {
return -1;
}
}
return this.buf[this.curChar++];
}
}
public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
int res = 0;
while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}
throw new InputMismatchException();
}
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void close() {
writer.close();
}
public void println(int i) {
writer.println(i);
}
}
}
0 Comments