Cod sursa(job #3295456)

Utilizator Barbu_MateiBarbu Matei Barbu_Matei Data 5 mai 2025 20:41:54
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>
using namespace std;

struct interval {
    int st, dr;
} v[100001];

bool comp(interval a, interval b) {
    return a.dr < b.dr;
}

int n;
unordered_map<int, int> dp;

int binSearch(int k, int limit) {
    int res = 0;
    for (int step = (1 << 20); step != 0; step >>= 1) {
        if (res + step <= limit && v[res + step].dr <= k) {
            res += step;
        }
    }
    return v[res].dr;
}

int main() {
    ifstream cin("heavymetal.in");
    ofstream cout("heavymetal.out");
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i].st >> v[i].dr;
    }
    sort(v + 1, v + n + 1, comp);
    dp[v[1].dr] = v[1].dr - v[1].st;
    int maxC = v[1].dr - v[1].st;
    for (int i = 2; i <= n; ++i) {
        int aux = binSearch(v[i].st, i - 1);
        if (dp[aux] + v[i].dr - v[i].st > dp[v[i].dr]) {
            dp[v[i].dr] = dp[aux] + v[i].dr - v[i].st;
        }
        maxC = max(maxC, dp[v[i].dr]);
        dp[v[i].dr] = max(dp[v[i].dr], maxC);
    }
    cout << dp[v[n].dr];
}