# Mountains TLE

This one.

## Question

Is my algorithm wrong, or is Java just slow? Oddly enough, it seems to pass the last test case.

## What I’ve Tried

I’ve downloaded the test data to see how many times the inner while loop in my code runs, and it’s never gone over the single-digit millions.

## My Work

import java.io.*;
import java.util.*;

public class Mountains {
public static void main(String[] args) throws IOException {
assert mtns.length == mtnNum;

int pairNum = 0;
TreeSet<Slope>[] slopes = new TreeSet[mtnNum];
for (int m = 0; m < mtnNum; m++) {
slopes[m] = new TreeSet<>();
for (int next = m + 1; next < mtnNum; next++) {
double slope = (double) (mtns[next] - mtns[m]) / (next - m);
if (next == m + 1 || slope >= slopes[m].last().slope) {
pairNum++;
}
}
}

long total = 0;
StringBuilder ans = new StringBuilder();
for (int q = 0; q < queryNum; q++) {
int ind = Integer.parseInt(query.nextToken()) - 1;
int amt = Integer.parseInt(query.nextToken());
mtns[ind] += amt;

pairNum -= slopes[ind].size();
// yes, this is the exact same loop used just 10 lines above
slopes[ind] = new TreeSet<>();
for (int next = ind + 1; next < mtnNum; next++) {
double slope = (double) (mtns[next] - mtns[ind]) / (next - ind);
if (next == ind + 1 || slope >= slopes[ind].last().slope) {
}
}
pairNum += slopes[ind].size();

for (int m = 0; m < ind; m++) {
double slope = (double) (mtns[ind] - mtns[m]) / (ind - m);
Slope obj = new Slope(ind, slope);
Slope compTo = slopes[m].lower(obj);
if (compTo != null && compTo.slope > slope) {
continue;
}
pairNum -= slopes[m].size();
slopes[m].remove(obj);  // because of how the treeset works

while (true) {
compTo = slopes[m].higher(obj);
if (compTo == null || compTo.slope >= slope) {
break;
}
slopes[m].remove(compTo);
total++;
}
pairNum += slopes[m].size();
}
ans.append(pairNum).append('\n');
}

System.out.print(ans);
System.out.println(total);
}

private static class Slope implements Comparable<Slope> {
public int to;
public double slope;

public Slope(int to, double slope) {
this.to = to;
this.slope = slope;
}

@Override

@Override
public String toString() { return String.format("(%d,%f)", to, slope); }
}
}

It maintains a monotonic set of slopes for each mountain.

It’s likely that Java is just slow; we observed the same with our TreeSet solution.

Nevermind- even with C++, my solution still TLEs:

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

// #include "debugging.hpp"

using namespace std;  // too many lol

int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);

int mtn_num;
cin >> mtn_num;
vector<int> mtns(mtn_num);
for (int& m : mtns) {
cin >> m;
}

int pair_num = 0;
vector<set<pair<int, double>>> slopes(mtn_num);
for (int m = 0; m < mtn_num; m++) {
for (int next = m + 1; next < mtn_num; next++) {
double slope = (double) (mtns[next] - mtns[m]) / (next - m);
if (slopes[m].empty() || slope >= slopes[m].rbegin()->second) {
slopes[m].insert({next, slope});
pair_num++;
}
}
}

int query_num;
cin >> query_num;
for (int q = 0; q < query_num; q++) {
int ind, amt;
cin >> ind >> amt;
int prev = mtns[--ind];
mtns[ind] += amt;

pair_num -= slopes[ind].size();
// yes, this is the exact same loop used just 10 lines above
slopes[ind].clear();
for (int next = ind + 1; next < mtn_num; next++) {
double slope = (double) (mtns[next] - mtns[ind]) / (next - ind);
if (slopes[ind].empty() || slope >= slopes[ind].rbegin()->second) {
slopes[ind].insert({next, slope});
}
}
pair_num += slopes[ind].size();

for (int m = 0; m < ind; m++) {
double new_ = (double) (mtns[ind] - mtns[m]) / (ind - m);
pair<int, double> obj{ind, new_};
auto comp = slopes[m].lower_bound(obj);
if (comp != slopes[m].begin() && (--comp)->second > new_) {
continue;
}

pair_num -= slopes[m].size();
double old = (double) (prev - mtns[m]) / (ind - m);
slopes[m].erase({ind, old});

auto higher = slopes[m].upper_bound(obj);
while (higher != slopes[m].end() && new_ > higher->second) {
higher = slopes[m].erase(higher);
}
slopes[m].insert(obj);

pair_num += slopes[m].size();
}

cout << pair_num << '\n';
}
}

The complexity should be correct though- I can’t figure out what’s taking so much time.

The analysis solution that uses sets takes more than half the time limit despite being relatively optimized, so that’s not too surprising. You may need one of the optimizations from that solution.