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?