Cod sursa(job #1630309)

Utilizator lflorin29Florin Laiu lflorin29 Data 5 martie 2016 00:58:54
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>

using namespace std;

struct Point
{
    int x, y;
    Point (int x = 0, int y = 0) : x(x), y(y) {};
    bool operator < (const Point &other) const {
        return x < other.x;
    }
};

const int MAX_N = 100007;

int N, OG[MAX_N * 2];
Point A[MAX_N];
vector<int>coordinates;

void Read()
{
    freopen("heavymetal.in", "r", stdin);
    scanf("%d", &N);
    for(int i = 0; i < N; ++i)
    {
        scanf("%d %d", &A[i].x, &A[i].y);
        coordinates.push_back(A[i].x);
        coordinates.push_back(A[i].y);
    }
}

void Init()
{
    sort(coordinates.begin(), coordinates.end());
    coordinates.resize(unique(coordinates.begin(), coordinates.end()) - coordinates.begin());
    for(int i = 0; i < N; ++i)
    {
        int p1 = lower_bound(coordinates.begin(), coordinates.end(), A[i].x) - coordinates.begin() + 1;
        int p2 = lower_bound(coordinates.begin(), coordinates.end(), A[i].y) - coordinates.begin() + 1;
        OG[p1] = A[i].x, OG[p2] = A[i].y;
        A[i].x = p1;
        A[i].y = p2;
    }
}

struct fenwick
{
   static const int lim = 2 * 100007;
   vector<int>aib;
   fenwick()
   {
       aib.resize(lim);
   }

   void update(int x, int val)
   {
       for(; x < lim; x += x &-x)
          aib[x] = max(aib[x] , val);
   }

   int que(int x)
   {
       int res = 0;
       for( ; x ; x -= x &-x)
        res = max(res , aib[x]);
       return res;
   }
};

void Solve()
{
    fenwick T;
    sort(A, A + N);
    int res = 0;
    for(int i = 0; i < N; ++i)
    {
        int val = T.que(A[i].x) + OG[A[i].y] - OG[A[i].x];
        res = max(res , val);
        T.update(A[i].y , val);
    }

    freopen("heavymetal.out", "w", stdout);
    printf("%d ", res);
}

int main() {
    Read();
    Init();
    Solve();
    return 0;
}