# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
276226 | stoyan_malinin | Teams (IOI15_teams) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "teams.h"
#include "grader.cpp"
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
struct Event
{
int type;
int pos;
pair <int, int> info;
Event(){}
Event(int type, int pos, pair <int, int> info)
{
this->type = type;
this->pos = pos;
this->info = info;
}
};
bool operator <(Event A, Event B)
{
if(A.pos!=B.pos) return A.pos<B.pos;
return A.type<B.type;
}
int n;
int *a, *b;
void init(int N, int A[], int B[])
{
n = N;
a = A;
b = B;
}
int can(int M, int K[])
{
multiset <pair <int, int>> s;
vector <Event> v;
for(int i = 0;i<n;i++)
{
v.push_back(Event(0, a[i], {b[i], a[i]}));
v.push_back(Event(2, b[i], {b[i], a[i]}));
}
for(int i = 0;i<M;i++)
{
v.push_back(Event(1, K[i], {K[i], K[i]}));
}
sort(v.begin(), v.end());
//for(Event e: v) cout << e.type << " -> " << e.info.first << " " << e.info.second << '\n';
for(Event e: v)
{
if(e.type==0)
{
s.insert(e.info);
}
else if(e.type==1)
{
if(s.size()<e.info.first) return 0;
for(int rem = 0;rem<e.info.first;rem++) s.erase(s.find(*s.begin()));
}
else if(e.type==2)
{
if(s.find(e.info)!=s.end()) s.erase(s.find(e.info));
}
//cout << e.type << " -> " << e.info.first << " " << e.info.second << " || " << s.size() << '\n';
}
return 1;
}
/*
4
1 2
2 3
2 3
2 4
2
2
1 3
2
1 1
*/