Pagini recente » Cod sursa (job #182449) | Cod sursa (job #1924166) | Cod sursa (job #2301431) | Cod sursa (job #2594913) | Cod sursa (job #2681424)
#include <fstream>
using namespace std;
long long a[200001], b[200001];
int L[200001], R[200001], f[200010], s[200010];
int n, i, nr, maxim, ap, gasit, j, usa, st, dr;
int main () {
ifstream fin ("pitici.in");
ofstream fout("pitici.out");
fin>>n;
for (i=1;i<=n;i++) {
fin>>a[i]; /// a[i] = cate kg slabeste un pitic care suna la usa i
s[i] = s[i-1] + a[i];
}
for (i=1;i<=n;i++)
fin>>b[i]; /// b[i] = cate kg tre sa slabeasca piticul de la casa i
/// pentru fiecare pitic aflam care este ultima usa
/// la care el trebuie sa sune
for (i=1;i<=n;i++) {
L[i] = i; /// cea mai din stanga usa la care suna
/// piticul i
/// mai am de calculat R[i] = cea mai din dreapta
/// usa la ca suna piticul i
st = i;
dr = n;
/// caut prima pozitie k unde s[k]-s[i-1] >= b[i]
while (st <= dr) {
int mid = (st + dr)/2;
if ( s[ mid ]-s[i-1] >= b[i] )
///s[ mid ]-s[i-1] = cat slabeste
///piticul i daca suna intre usile i
/// si mid inclusiv
dr = mid-1 ;
else
st = mid+1;
}
if (st > n)
R[i] = n;
else
R[i] = st;
}
/// avem un sir de n intervale L[i], R[i] care reprezinta
/// intre ce usi suna piticul i
for (i=1;i<=n;i++) {
f[ L[i] ]++;
f[ R[i]+1 ]--;
}
for (i=2;i<=n;i++) {
f[i] += f[i-1];
if (f[i] > maxim) {
maxim = f[i];
ap = 1;
} else
if (f[i] == maxim)
ap++;
}
fout<<maxim<<" "<<ap;
}
/**
1 2 4 5 6 6 6
4 2 8 10 14 6 17
X
L 1 2 3 4 5 6 7
R 3 2 4 5 7 6 7
X X
**/
/**
Se dau intervalele de indici de mai jos
si intre fiecare indici cresc toate elementele cu 1
care este maximul din sir si de cate ori apare
1 3
2 2
3 4
4 5
5 7
6 6
7 7
1 2 3 4 5 6 7
1 1 0 -1 -1
**/
/**
a 1 2 4 5 6 6 6
s 1 3 7 12 18 24 30
s[i] = a[1]+a[2] + ... + a[i]
folosind sirul s cum pot afla cat slabeste
piticul i daca ultima data suna la la usa j?
a, s, i, j
s[j] - s[i-1]
s[j] = a[1] + a[2] + ... + a[i-1]+a[i]+ ... + a[j]
s[i-1] = a[1] + a[2] + ... + a[i-1]
cu un i fixat, sirul
s[i] - s[i-1] piticul i suna intre usa i si usa i
s[i+1] - s[i-1] piticul i suna intre usa i si usa i+1
s[i+2] - s[i-1] piticul i suna intre usa i si usa i+2
s[i+3] - s[i-1] piticul i suna intre usa i si usa i+3
...
s[n] - s[i-1] piticul i suna intre usa i si usa n
reprezinta in ordine cate kg slabeste piticul i daca suna
ultia data la fiecare usa de dupa i
De exemplu, pentru i=3 sirul de mai sus arata:
a 1 2 4 5 6 6 6
s 1 3 7 12 18 24 30
s[i] - s[i-1] 4
s[i+1] - s[i-1] 9
s[i+2] - s[i-1] 15
s[i+3] - s[i-1] 21
s[n] - s[i-1] 27
4 2 8 10 14 6 17
**/