CCC14S4 help...

[quick cosmos]

Here is what I have so far
problem link: https://dmoj.ca/problem/ccc14s4

I took inputs, sorted them into events
for (Glass glass : glasses) {
events.add(new Event(glass.x1, glass.y1, glass.y2, glass.tintLevel));
events.add(new Event(glass.x2, glass.y1, glass.y2, -glass.tintLevel));
}

and converted them into arrays
TreeSet<Integer> yIntervals = new TreeSet<>();
for (Glass glass : glasses) {
yIntervals.add(glass.y1);
yIntervals.add(glass.y2);
}
Integer[] yValues = yIntervals.toArray(new Integer[0]);

here is my loop for every pair

for (Event event : events) {
int x = event.x;
int y1 = event.y1;
int y2 = event.y2;
int value = event.value;
totalArea += (x - prevX) * getArea(yValues, t, y1, y2, value);
prevX = x;
}

I'm struggling to come up with a working getArea method for this question.

[solid gull]

<@&987246399047479336> please have a look, thanks.

[solid gull]

While you are waiting for getting help, here are some tips to improve your experience:

Code is much easier to read if posted with syntax highlighting and proper formatting.

If nobody is calling back, that usually means that your question was not well asked and hence nobody feels confident enough answering. Try to use your time to elaborate, provide details, context, more code, examples and maybe some screenshots. With enough info, someone knows the answer for sure.

Don't forget to close your thread using the command </help-thread close:1027500463647621170> when your question has been answered, thanks.

Here is an AI assisted attempt to answer your question 🤖. Maybe it helps! In any case, a human is on the way 👍. To continue talking to the AI, you can use </chatgpt:1108714622413963314>.

It looks like you have started by taking inputs and sorting them into events. That's a good start!

To continue, you can now implement the algorithm to find the maximum number of glasses that can be stacked. Here's a step-by-step guide on how to do that:

1. Sort the events in ascending order based on their x-coordinate.
2. Initialize a variable maxHeight to store the maximum height of the stack.
3. Iterate through each event in the sorted list:
   • If it is an opening event (start of a glass), increment a counter variable currentHeight.
   • If it is a closing event (end of a glass), decrement currentHeight.
   • Update maxHeight with the maximum value between maxHeight and currentHeight.
4. Output the value of maxHeight.

Here's an example implementation in Java:

import java.util.*;

class Glass {
    int x, h;

    public Glass(int x, int h) {
        this.x = x;
        this.h = h;
    }
}

class Event implements Comparable<Event> {
    int x, type;

    public Event(int x, int type) {
        this.x = x;
        this.type = type;
    }

    @Override
    public int compareTo(Event other) {
        if (this.x != other.x)
            return Integer.compare(this.x, other.x);
        return Integer.compare(this.type, other.type);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        List<Glass> glasses = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int h = sc.nextInt();
            glasses.add(new Glass(x, h));
        }
        
        List<Event> events = new ArrayList<>();
        
        for (Glass glass : glasses) {
            events.add(new Event(glass.x, 1));
            events.add(new Event(glass.x + glass.h, -1));
        }
        
        Collections.sort(events);
        
        int maxHeight = 0;
        int currentHeight = 0;
        
        for (Event event : events) {
            if (event.type == 1)
                currentHeight++;
            else
                currentHeight--;
            
            maxHeight = Math.max(maxHeight, currentHeight);
        }
        
        System.out.println(maxHeight);
    }
}

This should give you the correct output for the problem. Let me know if you have any further questions!

[azure spindle]

They just want the tint levels for each 1x1 square. There's like 3.7Terabytes of potential 1x1 squares of which most are unused.

[quick cosmos]

I think they want the area of glass which the tint level is equal or more than the given t

[azure spindle]

same thing

pardon, you'll have to filter the ones >= T

and that will be the area

The count of those 1x1 squares over T

It's a 'histogram' problem.