OJI 2023 S3
#include<fstream>
#include<vector>
#include<algorithm>
#include<set>
#include<utility>
#include<iterator>
#define ull unsigned long long
using namespace std;
struct copil
{
ull start;
ull finish;
bool p;
};
ifstream fin(“fotbal.in”);
ofstream fout(“fotbal.out”);
vector<copil>V;
vector<vector<ull> >Pascal;
bool cmp(copil a, copil b){
if(a.finish==b.finish)
{
if(a.start==b.start)
return (a.p==1);
return a.start<b.start;
}
return a.finish<b.finish;
}
int main()
{
int N,K;
fin>>N>>K;
V.resize(N);
for(int i=0; i<N; ++i)
{
fin>>V[i].start>>V[i].finish>>V[i].p;
}
sort(V.begin(),V.end(),cmp);
if(K==2)
{
ull cnt=0;
for(int i=0; i<V.size(); i++)
{
if(V[i].p==false)
{
int j=i-1;
while(j<=0)
{
if(V[i].start<=V[j].finish && V[j].p!=V[i].p)
cnt++;
j—;
}
j=i+1;
while(j<V.size())
{
if(V[j].start<=V[i].finish && V[j].p!=V[i].p)
cnt++;
j++;
}
}
}
fout<<cnt<<endl;
fin.close();
fout.close();
return 0;
}
vector<pair<int, set<int> > >C((V.end()-1)->finish+1);
for(int i=0; i<C.size(); ++i)
C[i].first=0;
for(int i=0; i<V.size(); ++i)
{
for(int j=V[i].start; j<=V[i].finish; ++j)
{
C[j].first++;
C[j].second.insert(i);
}
}
set<set<int> >P;
for(int i=0; i<C.size(); ++i)
{
if(C[i].first>=K)
P.insert(C[i].second);
}
ull max_size=0;
for(set<set<int> >::iterator it=P.begin(); it!=P.end(); ++it)
{
max_size=max(max_size, (ull)it->size());
}
max_size;
Pascal.resize(max_size+1);
for(int i=0; i<Pascal.size();++i)
{
Pascal[i].resize(i+1, 0);
}
for(int i=0; i<Pascal.size(); ++i)
Pascal[i]=Pascal[i][i]=1;
for(int i=2; i<Pascal.size(); ++i)
{
for(int j=1; j<min(K,(int)Pascal[i].size()-1); ++j)
Pascal[i][j]=Pascal[i-1][j]+Pascal[i-1][j-1];
}
int cnt=0;
for(set<set<int> >::iterator it=P.begin(); it!=P.end();++it)
{
for(int i=it->size()-1;i>=K-1; —i)
{
cnt+=Pascal[i][K-1];
}
}
fout<<cnt;
fin.close();
fout.close();
return 0;
}
BOTOROGEANU ANDREI-PETRU (andrei_botorogeanu)