Cod sursa(job #2681424)

Utilizator mariusn01Marius Nicoli mariusn01 Data 5 decembrie 2020 14:09:15
Problema Principiul includerii si excluderii Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.99 kb
#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

**/