Для «МЕНЬШЕЙ» части списка [begin, UPPER_bound): все эти поддоны можно поставить на наш поддон по ДЛИНЕ, и только некоторый хвост [some_pallet, upper_bound) — по ширине. Находим этот кусок и исключаем из дерева.
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <chrono>
#include <set>
#include <fstream>
using namespace std;
int type = 0;
struct comparator {
int operator() (const pair<double, double>& l, const pair<double, double>& r) const {
if (type == 0) {
return l.first < r.first;
}
else {
return l.second > r.second;
}
}
};
class Solnew {
public:
set<pair<double, double>, comparator> st;
void proccess(pair<double, double>& p) {
auto it1 = st.upper_bound(p);
int flag = 0;
if (it1 == st.end() || it1->second <= p.second) {
st.insert(p);
flag = 1;
it1--;
}
if (flag && it1 != st.begin()) {
type = 1;
auto it2 = st.lower_bound(p);
type = 0;
if (it2 == st.end()) {
it2 = st.begin();
}
else {
it2++;
}
st.erase(it2, it1);
}
}
};
int main() {
ifstream f("input.txt");
Solnew s;
double count;
f >> count;
for (double i = 0; i < count; ++i) {
double left;
double right;
f >> left;
f >> right;
pair<double, double> p = { left,right };
double l = max(p.first, p.second);
double r = min(p.first, p.second);
p.first = l;
p.second = r;
s.proccess(p);
}
cout << s.st.size();
return 0;
}#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <string>
#include <fstream>
#include <sstream>
#include <iomanip>
using namespace std;
class Sol {
public:
vector<int> vec;
int sum = 0;
vector<long long> facts;
vector<long long> re_facts;
long long Z = 1000000007;
long long N = 0;
long long product_of_facts = 1;
long long inv_N = 1;
long long Factorial(int n)
{
long long f = 1;
if ((n == 0) || (n == 1))
f = 1;
else
for (int i = 1; i <= n; i++) {
f *= i;
f = f % Z;
}
return f;
}
long long C(long long n, long long k) {
return facts[n] * re_facts[k] * re_facts[n - k];
}
int DP(int k,int t,int i,int j){
if (k==-1 || t==0) return 1;
for (int v = 0; v < min(vec[k], t); ++v) {
int del1 = 0;
int del2 = 0;
if (v > 0) del1 = 1;
if (v<vec[k]) del2 = 1;
sum += DP(k-1,t-v,i-del1,j-del2)*C(t,v)*C(N-t,vec[k]-v);
}
return 1;
}
long long gcd(long long a, long long b, long long& x, long long& y) {
if (a == 0) {
x = 0; y = 1;
return b;
}
long long x1, y1;
long long d = gcd(b % a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}
};
int main() {
ifstream f("input.txt");
Sol s;
long long count;
f >> count;
for (int i = 0; i <= 500; ++i) {
s.facts.push_back(s.Factorial(i));
long long x;
long long y;
s.gcd(s.facts[s.facts.size() - 1] % s.Z, s.Z, x, y);
if (x < 0) x += s.Z;
s.re_facts.push_back(x);
}
for (long long i = 0; i < count; ++i) {
long long tmp;
f >> tmp;
s.vec.push_back(tmp);
s.product_of_facts *= s.facts[tmp];
s.product_of_facts = s.product_of_facts % s.Z;
s.N += tmp;
}
long long x;
long long y;
s.gcd(s.N % s.Z, s.Z, x, y);
if (x < 0) x += s.Z;
s.inv_N = x;
long long n = s.vec.size();
for (int i = 1; i < s.vec.size();++i) s.DP(s.vec.size()-1, s.N / 2, i, i);
cout << s.sum;
return 0;
}#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <string>
#include <fstream>
#include <sstream>
#include <iomanip>
using namespace std;
class Sol {
public:
long long num = 0;
vector<long long> starter;
long long otv = 0;
long long border = 0;
long long summer = 0;
unordered_map<long long, long long> unsetleft;
unordered_map<long long, long long> unsetright;
void rec(vector<long long> vec, long long counter, long long mn) {
if (counter == border) {
if (unsetleft.size() == unsetright.size()) {
otv += mn;
}
summer += mn;
return;
}
for (long long i = 0; i < vec.size(); ++i) {
if (vec[i] > 0) {
vec[i]--;
if (unsetleft.find(i) == unsetleft.end()) {
unsetleft.emplace(i, 1);
}
else {
unsetleft[i]++;
}
long long mem = unsetright[i];
if (vec[i] == 0) unsetright.erase(i);
rec(vec, counter + 1, mn * (vec[i] + 1));
if (vec[i] == 0) unsetright.emplace(i,mem);
if (unsetleft[i] == 1) {
unsetleft.erase(i);
}
else {
unsetleft[i]--;
}
vec[i]++;
}
}
}
long long gcd(long long a, long long b, long long& x, long long& y) {
if (a == 0) {
x = 0; y = 1;
return b;
}
long long x1, y1;
long long d = gcd(b % a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}
};
int main() {
ifstream f("input.txt");
Sol s;
long long count;
f >> count;
vector<long long> vec;
long long sch = 0;
for (long long i = 0; i < count; ++i) {
long long tmp;
f >> tmp;
s.unsetright.emplace(i,1);
vec.push_back(tmp);
sch += tmp;
}
s.border = sch / 2;
s.rec(vec, 0, 1);
long long P = s.otv;
long long Q = s.summer;
long long Z = 1000000007;
long long x;
long long y;
s.gcd(Q % Z, Z, x, y);
double res = ((P % Z) * x) % Z;
if (res < 0) res += Z;
cout << fixed << setprecision(0) << res;
//cout << s.bad;
return 0;
}
Добавил сортировку точек и все сработало!
Спасибо!