Cod sursa(job #1562360)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 4 ianuarie 2016 23:52:19
Problema Pitici Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <algorithm>
#include <fstream>
using namespace std;
ifstream cin("pitici4.in");
ofstream cout("pitici4.out");
const int MAX = 200001;
struct grup
{
    int st, dr, nr;
}v[MAX], vord[MAX];
int n, ngr, dp[MAX];
bool cmp(grup a, grup b)
{
    return (a.dr < b.dr) or (a.dr == b.dr and a.st < b.st);
}

char *buf;
int pos, lgbuf;
int read_int(){
    while(buf[pos]<'0' or '9'<buf[pos])
        pos++;
    int ans = 0;
    while('0'<=buf[pos] and buf[pos]<='9'){
        ans = ans*10 + buf[pos] - '0';
        pos++;
    }
    return ans;
}
vector <int> ldr[MAX];
int main()
{
    cin.seekg(0, cin.end);
    lgbuf = cin.tellg();
    cin.seekg(0, cin.beg);
    buf = new char[lgbuf];
    cin.read(buf, lgbuf);
    //cin>>n;
    n = read_int();
    for(int i=1; i<=n; ++i){
        int a, b;
        a = read_int();
        b = read_int();
        //cin>>a>>b;
        v[i].st = a + 1;
        v[i].dr = n - b;
        if(v[i].st > v[i].dr)
            v[i].st = v[i].dr = 0;
    }

    for(int i=1; i<=n; i++)
        ldr[ v[i].st ].push_back(i);
    int cnt = 0;
    for(int i=0; i<=n; i++){
        for(int j=0; j<ldr[i].size(); j++){
            cnt++;
            vord[cnt] = v[ ldr[i][j] ];
        }
        ldr[i].clear();
    }

    for(int i=1; i<=n; i++)
        ldr[ vord[i].dr ].push_back(i);
    cnt = 0;
    for(int i=0; i<=n; i++){
        for(int j=0; j<ldr[i].size(); j++){
            cnt++;
            v[cnt] = vord[ ldr[i][j] ];
        }
        ldr[i].clear();
    }

    for(int i=1; i<=n; ++i){
        if(v[ngr].st != v[i].st or v[ngr].dr != v[i].dr){
            ngr++;
            v[ngr] = v[i];
        }
        v[ngr].nr++;
    }

    for(int i=1; i<=ngr; ++i)
        if(v[i].nr > (v[i].dr - v[i].st + 1))
            v[i].nr = v[i].dr - v[i].st + 1;

    int last = n;
    for(int i=ngr; i>=1; i--)
        for(; last>v[i].dr; last--)
            vord[last].nr = i;

    for(int i=1; i<=ngr; ++i)
    {
        dp[i] = dp[i-1];
        if(dp[i] < dp[ vord[ v[i].st ].nr  ] + v[i].nr)
            dp[i] = dp[ vord[ v[i].st ].nr  ] + v[i].nr;
    }

    cout<<dp[ngr];
    return 0;
}