| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 276694 | 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;
const int MAXN = 5e5 + 5;
struct SegmentTree
{
int val;
int l, r;
SegmentTree *L, *R;
SegmentTree(){}
SegmentTree(int l, int r)
{
this->val = 0;
this->l = l;
this->r = r;
this->L = nullptr;
this->R = nullptr;
}
void copyFrom(SegmentTree *other)
{
l = other->l;
r = other->r;
val = other->val;
}
void build()
{
if(l==r) return;
L = new SegmentTree(l, (l+r)/2);
R = new SegmentTree((l+r)/2+1, r);
L->build();
R->build();
}
int query(int ql, int qr)
{
if(l>=ql && r<=qr) return val;
if(r<ql || l>qr) return 0;
return L->query(ql, qr) + R->query(ql, qr);
}
void update(int q, int change, SegmentTree *other)
{
copyFrom(other);
//cout << l << " " << r << " -> " << q << '\n';
if(l==r && l==q)
{
val += change;
return;
}
if(other->L->l<=q && q<=other->L->r)
{
L = new SegmentTree(other->L->l, other->L->r);
L->update(q, change, other->L);
}
else
{
L = other->L;
}
if(other->R->l<=q && q<=other->R->r)
{
R = new SegmentTree(other->R->l, other->R->r);
R->update(q, change, other->R);
}
else
{
R = other->R;
}
val = L->val + R->val;
}
};
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;
int dp[MAXN];
SegmentTree *T[MAXN];
vector <int> start2End[MAXN];
SegmentTree* createTree()
{
return new SegmentTree(1, n);
}
int getInside(int x1, int x2, int y1, int y2)
{
if(x1>x2 || y1>y2) return 0;
int ans = T[x2]->query(y1, y2);
if(x1!=0) ans -= T[x1-1]->query(y1, y2);
return ans;
}
void init(int N, int A[], int B[])
{
n = N;
a = A;
b = B;
for(int i = 0;i<n;i++)
start2End[ a[i] ].push_back(b[i]);
T[0] = createTree();
T[0]->build();
for(int i = 1;i<=n;i++)
{
T[i] = T[i-1];
for(int x: start2End[i])
{
SegmentTree *buff = createTree();
buff->update(x, +1, T[i]);
T[i] = buff;
}
}
/*
while(true)
{
int x1, x2, y1, y2;
cin >> x1 >> x2 >> y1 >> y2;
cout << getInside(x1, x2, y1, y2) << '\n';
}
*/
}
int slowSolve(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;
}
int can(int M, int K[])
{
if(M>sqrt(n)) return slowSolve(M, K);
sort(K, K+M);
for(int i = 0;i<=M;i++) dp[i] = 0;
for(int i = 0;i<M;i++)
{
dp[i] = getInside(1, K[i], K[i], n) - K[i];
for(int j = 0;j<i;j++)
{
dp[i] = min(dp[i], dp[j] + getInside(K[j]+1, K[i], K[i], n) - K[i]);
}
}
int minVal = MAXN;
for(int i = 0;i<M;i++) minVal = min(minVal, dp[i]);
if(minVal<0) return 0;
return 1;
}
/*
4
1 2
2 3
2 3
2 4
2
2
1 3
2
1 1
*/