Submission #1185795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185795		vibhas	Advertisement 2 (JOI23_ho_t2)	Java	100 / 100	1549 ms	191980 KiB

Main

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][]reach = new int[n+1][3];
        int[][]influence = new int[n+1][3];
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            reach[i][0] = x;
            reach[i][1] = x + e;
            reach[i][2] = i;

            influence[i][0] = x;
            influence[i][1] = x - e;
            influence[i][2] = i;
        }
        Arrays.sort(reach, 1, n + 1, (X, Y) -> {
            if (X[0] != Y[0]) return Integer.compare(X[0], Y[0]);
            if (X[1] != Y[1]) return Integer.compare(Y[1], X[1]);
            return Integer.compare(X[2], Y[2]);
        });

        Arrays.sort(influence, 1, n + 1, (X, Y) -> {
            if (X[0] != Y[0]) return Integer.compare(X[0], Y[0]);
            if (X[1] != Y[1]) return Integer.compare(Y[1], X[1]);
            return Integer.compare(X[2], Y[2]);
        });
        List<Integer> list_reach = new ArrayList<>();
        List<Integer> list_influence = new ArrayList<>();
        for (int i = n; i >= 1; i--) {
            if (list_reach.isEmpty() || reach[i][1] != reach[list_reach.get(list_reach.size() - 1)][1] || reach[i][0] != reach[list_reach.get(list_reach.size() - 1)][0]) {
                while (!list_reach.isEmpty()) {
                    int back = list_reach.get(list_reach.size() - 1);
                    if (reach[i][1] >= reach[back][1] || (reach[i][1] == reach[back][1] && reach[i][0] != reach[back][0])) {
                        list_reach.remove(list_reach.size() - 1);
                    } else {
                        break;
                    }
                }
                list_reach.add(i);
            }
        }

        Collections.reverse(list_reach);

        for (int i = 1; i <= n; i++) {
            while (!list_influence.isEmpty() && influence[i][1] <= influence[list_influence.get(list_influence.size() - 1)][1]) {
                list_influence.remove(list_influence.size() - 1);
            }
            list_influence.add(i);
        }

        int ans = 0, i = 0, j = 0;
        while (i < list_reach.size() && j < list_influence.size()) {
            int i1 = list_reach.get(i), i2 = list_influence.get(j);
            if (reach[i1][0] < influence[i2][0]) {
                i++;
            } else if (reach[i1][0] > influence[i2][0]) {
                j++;
            } else {
                if (reach[i1][2] == influence[i2][2]) ans++;
                i++;
                j++;
            }
        }
        System.out.println(ans);
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31