Najbrojniji presek intervala

Radi se o zadatku na linku : https://petlja.org/biblioteka/r/problemi/zbirka-napredni-nivo/najbrojniji_presek_intervala

Slao sam kod koji je gotovo isti kao jedan od onih iz rešenja zadatka više puta, uvek sa po nekom ispravkom (stavljao sam i long long umesto int iako su brojevi do milijardu). Kao i svaki kod iz rešenja (govorim samo za C++) dobijao sam WA na 2 i 7 primeru. Evo koda:

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define ldb long double
#define ll long long
#define vi vector<int>
#define PB push_back
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define Fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define w(x) cout<<#x<<"  :  "<<x<<endl;
#define MAX (int)2e5+5
#define INF (ll)1e18

int main()
{
    Fast;
    int n;
    cin>>n;
    vector<pair<int,bool>> a(2*n);
    for(int i=0; i<n; ++i) {
        cin>>a[2*i].F>>a[2*i+1].F;
        a[2*i+1].F--;
        a[2*i].S=0;
        a[2*i+1].S=1;
    }
    sort(all(a));
    int c=0,ans=0;
    for(int i=0; i<2*n; ++i) {
        if(a[i].S==0) c++;
        else c--;
        ans=max(c,ans);
    }
    cout<<ans;
    return 0;
}

Međutim, kada sam ga otkucao na malo drugačiji način (koristio sam uvek push_back umesto da napravim u startu vektor od 2*n članova), dobijam OK na svim test primerima. Ima li neko ideju zašto kod iznad ne radi?

Evo koda koji radi:

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define PB push_back
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define Fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main()
{
    Fast;
    int n,ans=0,x,y,c=0;
    cin>>n;
    vector<pair<int,bool>> a;
    for(int i=0; i<n; ++i) {
        cin>>x>>y;
        a.PB({x,0});
        a.PB({y-1,1});
    }
    sort(all(a));
    for(int i=0; i<n; ++i) {
        if(!a[i].S) c++;
        else c--;
        ans=max(ans,c);
    }
    cout<<ans;
    return 0;
}

btw iz nekog razloga mi je text editor na forumu sam izbacio neke minuseve i znak *. Kako da kucam kod a da ostane isti, vidim da su i sve linije povučene na levo?

Ako samo prekopiras kod u tekst poruke, * se (na primer) tumaci kao znak za bold. Da bi ovo iskljucio i formatirao kod kao kod (sa tabovima itd) umesto kao tekst, okruzi ga sa ~~~. Na primer

~~~
for(int i = 0; i < n; i++); // ...
~~~

daje

    for(int i = 0; i < n; i++) ; // ...

Koliko vidim ovi programi nisu potpuno isti (ne mogu da komentarisem o tacnosti, nisam pogledao zadatak). Prvi:

sort(all(a));
int c = 0, ans = 0;
for(int i = 0; i < 2*n; ++i) {  // ...

Drugi:

sort(all(a));
for(int i = 0; i < n; i++) {  // do n, ne 2n

@dd
Sada i ja vidim da je n, a ne 2*n sto je zapravo greška jer taj vektor ima 2*n clanova koje sve treba proveriti. Ipak, kod sa n radi :thinking: . Pretpostavljam da je neki problem sa checkerom…

Štaviše, kada u kodu iz rešenja 2*n zamenim sa n sve prolazi.

Inace, ako hoces da imas * u tekstu a da se ne tumaci kao italic (i kod generalno), mozes ga okruziti sa `:

`2*n`

postaje 2*n

1 Like