Pagini recente » Cod sursa (job #238899) | Cod sursa (job #296339) | Cod sursa (job #2204563) | Cod sursa (job #286752) | Cod sursa (job #1562360)
#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;
}