link to contest?
1 Like
I used Segment Tree. Here’s my solution
import java.math.*;
import java.io.*;
import java.util.*;
class Solution {
static class SegmentTreeNode{
public int max;
public int l, r;
public SegmentTreeNode left, right;
public SegmentTreeNode(int l, int r) {
this.l = l;
this.r = r;
}
}
static class SegmentTree{
private static SegmentTreeNode root = null;
int ar[];
public SegmentTree(int ar[]) {
this.ar = ar;
root = buildTree(root, ar, 0, ar.length - 1);
}
public SegmentTreeNode buildTree(SegmentTreeNode n, int ar[], int l, int r) {
if (n == null)
n = new SegmentTreeNode(l, r);
if (l < r) {
int mid = (l + r) >> 1;
n.left = buildTree(n.left, ar, l, mid);
n.right = buildTree(n.right, ar, mid + 1, r);
n.max = Math.max(n.left.max, n.right.max);
}
else if (l == r) {
n.max = ar[l];
n.left = null;
n.right = null;
}
else
return null;
return n;
}
public int maxquery(int l, int r) {
return max(root, l, r);
}
public int max(SegmentTreeNode n, int l, int r) {
if (n == null) {
return Integer.MIN_VALUE;
}
if (n.l >= l && n.r <= r) {
return n.max;
}
if (n.l > r || n.r < l) {
return Integer.MIN_VALUE;
}
return Math.max(max(n.left, l, r), max(n.right, l, r));
}
}
public static void main(String[] args) throws Exception {
InputReader in = new InputReader(System.in);
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
int tc = in.readInt();
for (int t = 0; t < tc; t++) {
int n = in.readInt();
int q = in.readInt();
int col[] = new int[n];
long qan[] = new long[n];
for (int i = 0; i < n; i++) {
col[i] = in.readInt();
}
for (int i = 0; i < n; i++) {
qan[i] = in.readInt();
}
SegmentTree segmentTree = new SegmentTree(col);
Map<Integer, Integer> colShopMap = new HashMap<>();
for (int i = 0; i < n; i++) {
colShopMap.put(col[i], i);
}
for (int qc = 0; qc < q; qc++) {
int type = in.readInt();
if (type == 1) {
int l = in.readInt() - 1;
int r = in.readInt() - 1;
long qt = in.readLong();
int maxCol = segmentTree.maxquery(l, r);
int shopId = colShopMap.get(maxCol);
qan[shopId] += qt;
}
else {
int v = in.readInt();
int shop = in.readInt() - 1;
int l = Math.max(0, shop - v);
int r = Math.min(n - 1, shop + v);
int qt = in.readInt();
int thres = in.readInt();
int maxCol = segmentTree.maxquery(l, r);
if (maxCol >= thres) {
int shopId = colShopMap.get(maxCol);
if (qan[shopId] >= qt) {
qan[shopId] -= qt;
out.write(Integer.toString(shopId + 1));
}
else {
out.write("No purchase");
}
}
else {
out.write("No purchase");
}
out.newLine();
}
}
out.newLine();
}
out.close();
}
}
class InputReader {
private boolean finished = false;
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int peek() {
if (numChars == -1)
return -1;
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
return -1;
}
if (numChars <= 0)
return -1;
}
return buf[curChar];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long readLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String readString() {
int length = readInt();
if (length < 0)
return null;
byte[] bytes = new byte[length];
for (int i = 0; i < length; i++)
bytes[i] = (byte) read();
try {
return new String(bytes, "UTF-8");
} catch (UnsupportedEncodingException e) {
return new String(bytes);
}
}
public static boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private String readLine0() {
StringBuffer buf = new StringBuffer();
int c = read();
while (c != '\n' && c != -1) {
if (c != '\r')
buf.appendCodePoint(c);
c = read();
}
return buf.toString();
}
public String readLine() {
String s = readLine0();
while (s.trim().length() == 0)
s = readLine0();
return s;
}
public String readLine(boolean ignoreEmptyLines) {
if (ignoreEmptyLines)
return readLine();
else
return readLine0();
}
public BigInteger readBigInteger() {
try {
return new BigInteger(readString());
} catch (NumberFormatException e) {
throw new InputMismatchException();
}
}
public char readCharacter() {
int c = read();
while (isSpaceChar(c))
c = read();
return (char) c;
}
public double readDouble() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
double res = 0;
while (!isSpaceChar(c) && c != '.') {
if (c == 'e' || c == 'E')
return res * Math.pow(10, readInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
}
if (c == '.') {
c = read();
double m = 1;
while (!isSpaceChar(c)) {
if (c == 'e' || c == 'E')
return res * Math.pow(10, readInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
m /= 10;
res += (c - '0') * m;
c = read();
}
}
return res * sgn;
}
public boolean isExhausted() {
int value;
while (isSpaceChar(value = peek()) && value != -1)
read();
return value == -1;
}
public String next() {
return readString();
}
public boolean readBoolean() {
return readInt() == 1;
}
}i asked 'em too, but they haven’t given me one yet
Can I know when and where did this challenge took place
If I am not wrong they invited 4 stars and above for the challenge. The problems are not visible now, so link of the contest is of no use. It happened today from 4pm to 7pm IST.
In the last loop we should iterate over rev_graph instead of graph which was also mistake
congrachulashunz
2 Likes
I did it using Segment Tree.First I made a query for the max quality index first and then an update operation for that index if it is valid.
pair<pii, int> v[4 * N];
pii val[N];
int len, x, y, w, z, qt, th, ans, pass;
void build(int id, int cx, int cy)
{
if (cx == cy)
{
v[id] = {val[cx], cx};
return;
}
int mid = (cx + cy) / 2;
build(2 * id, cx, mid);
build(2 * id + 1, mid + 1, cy);
x = max(v[2 * id].ff.ff, v[2 * id + 1].ff.ff);
if (x == v[2 * id].ff.ff) v[id] = v[2 * id];
else v[id] = v[2 * id + 1];
}
void update(int id, int cx, int cy)
{
if (x < cx or x > cy) return;
if (cx == cy and x == cx)
{
val[cx].ss += w;
v[id] = {val[cx], cx};
return;
}
int mid = (cx + cy) / 2;
update(2 * id, cx, mid);
update(2 * id + 1, mid + 1, cy);
z = max(v[2 * id].ff.ff, v[2 * id + 1].ff.ff);
if (z == v[2 * id].ff.ff) v[id] = v[2 * id];
else v[id] = v[2 * id + 1];
}
int query_id(int id, int cx, int cy)
{
if (y < cx or x > cy) return -1;
if (x <= cx and cy <= y) return v[id].ss;
int mid = (cx + cy) / 2;
int left = -1, right = -1;
left = query_id(2 * id, cx, mid);
right = query_id(2 * id + 1, mid + 1, cy);
int ans = -1;
if (left != -1) ans = left;
if (right != -1)
{
if (left == -1) ans = right;
else if (val[left].ff < val[right].ff) ans = right;
}
return ans;
}
// remember to decrease the quantity
void query_update(int id, int cx, int cy)
{
if (x < cx or x > cy) return;
if (cx == cy and x == cx)
{
val[cx].ss -= qt;
v[id] = {val[cx], cx};
return;
}
int mid = (cx + cy) / 2;
query_update(2 * id, cx, mid);
query_update(2 * id + 1, mid + 1, cy);
z = max(v[2 * id].ff.ff, v[2 * id + 1].ff.ff);
if (z == v[2 * id].ff.ff) v[id] = v[2 * id];
else v[id] = v[2 * id + 1];
}
void solve()
{
fo(i, 0, 4 * N - 1) v[i] = {{0, 0}, -1};
int n, q;
cin >> n >> q;
fo(i, 0, n - 1) cin >> val[i].ff;
fo(i, 0, n - 1) cin >> val[i].ss;
build(1, 0, n - 1);
while (q--)
{
cin >> z;
if (z == 1)
{
cin >> x >> y >> w;
x--, y--;
x = query_id(1, 0, n - 1);
update(1, 0, n - 1);
}
else
{
cin >> len >> z >> qt >> th;
z--;
x = max(0LL, z - len);
y = min(n - 1, z + len);
x = query_id(1, 0, n - 1);
if (val[x].ff < th or val[x].ss < qt) cout << "No purchase\n";
else
{
query_update(1, 0, n - 1);
x++;
cout << x << endl;
}
}
}
}
“
Here’s the problem. I just solved this problem yesterday. Copy pasted my code with minor changes and got 92%. Didn’t bother to debug for 100. 
Initially I write the code in Python and I got 82% and then I wrote the same code in cpp, it gave me 100%
they invited me too!!
Can anyone say when will the results be published?Also anyone did 700 score???
Since your highest rating is >= 1800
ohhhhhhhhhh…sad. my highest is 3 star 
Basically we store a map < quality, index> and any data structure to answer range max query.
Now for query 1
Find max in given range
Use map to get its index
Update the quantity at that index
For query 2
Find max in range
Find its index using map
Now if the quality is not less than threshold and quantity is also not less than required
Make purchase, reduce quantity at this index
Else say, No purchase.
Yup, I scored 700 
3 Likes
Congratulations…Actually I have just started learning java so i wasn’t able to do that…
I got left by 2 points…AHHH
should have given Lunchtime. :’(
anyone has done debugging java ? what was the problem in that code? is it Multiplication overflow ?