# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1092931 | shivansh0809 | Holiday (IOI14_holiday) | C++17 | 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 "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct PersistentSegTree
{ // find_kth returns the kth smallest element in the array in [l, r)
struct Vertex
{
Vertex *l, *r;
int sum;
int k_sum;
Vertex(int val) : l(nullptr), r(nullptr), sum(val), k_sum(0) {}
Vertex(int val, int k_sum) : l(nullptr), r(nullptr), sum(val), k_sum(k_sum) {}
Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0), k_sum(0)
{
if (l)
sum += l->sum, k_sum += l->k_sum;
if (r)
sum += r->sum, k_sum += r->k_sum;
}
};
vector<Vertex *> roots;
map<int, pair<int, int>> compress;
int n;
PersistentSegTree(vector<int> v) : n(v.size())
{