I was trying to write an ordered map, which will work like a frequency table. I thought it would be a good addition because ordered_set doesn't support duplicate entries very well.

Here's some code I wrote:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;

template<class Node_CItr, class Node_Itr, class Cmp_Fn, class _Alloc>
struct order_statistics_frequency_list_update {
  typedef size_t metadata_type;
  void operator()(Node_Itr it, Node_CItr end_it) {
    cout<<(*it)->first<<"**"<<(*it)->second<<endl;
    metadata_type x = (*it)->second;
    const auto left_child = it.get_l_child();
    const auto right_child = it.get_r_child();
    if (left_child != end_it) {
      x += left_child.get_metadata();
    } 
    if (right_child != end_it) {
      x += right_child.get_metadata();
    }
    const_cast<metadata_type&>(it.get_metadata()) = x;
  }
  size_t order_of_key(int64_t key) {
    size_t order = 0;
    auto it = node_begin();
    const auto end = node_end();
    while (it != end) {
      const auto left_child = it.get_l_child();
      const auto right_child = it.get_r_child();
      if (Cmp_Fn()(key, (*it)->first)) {
        it = left_child;
      } else {
        if (left_child != end) order += left_child.get_metadata();
        if (key == (*it)->first) return order;
        order += (*it)->second;
        it = right_child;
      }
    }
    return order;
  }
  metadata_type find_by_order(size_t order) {
    auto it = node_begin();
    const auto end = node_end();
    while (it != end) {
      const auto left_child = it.get_l_child();
      const auto right_child = it.get_r_child();
      size_t lchild_size = (left_child == end)? 0 : left_child.get_metadata();
      if (order >= lchild_size) {
        order -= lchild_size;
        if (order >= (*it)->second) {
          order -= (*it)->second;
          it = right_child;
        } else return (*it)->first;
      } else {
        it = left_child;
      }
    }
    return (*it)->first;
  }
  virtual Node_CItr node_begin() const = 0;
  virtual Node_CItr node_end() const = 0;
};


typedef tree<
  int64_t, 
  size_t, 
  less<int64_t>, 
  rb_tree_tag, 
  order_statistics_frequency_list_update
> ordered_multiset;

Basically, it changes the update policy to take the frequencies of the keys into account when calculating find_by_order and order_of_key.

However, in the end. I found that this wouldn't work. The tree in pb_ds was implemented only to update the internal data of the node when the structure surrounding that node has changed (nodes shifted), which would only happen when a node is added or deleted. Additionally the structure puts in the key first, operates on the key, then puts in the value.

That means if I change the value (frequency of key), then call find_by_order, the answer will be completely wrong because the internal data didn't update. There's also times where I inserted key value pairs and it didn't update my frequency into the internal data, resulting in wrong answers.

So in the end I figured it wouldn't work. It was a fairly fruitless exploration for me. But at least I found some good links, so if you are interested in PBDS, here they are:

https://ideone.com/jOxlgl (an example of custom defined operator)

https://ideone.com/JlJ86R (print tree)

A few useful blogs:

https://codeforces.me/blog/entry/11080 (basics)

https://codeforces.me/blog/entry/13279 (creating custom policies, tutorial-ish)

https://codeforces.me/blog/entry/110677 (sum of segment)

https://neveropen.tech/interval-tree-using-gnu-tree-based-container/

GCC documentation? https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures_design.html#pbds.design.container.tree

Hopefully this is helpful if you're interested in learning about PBDS as well.

So today I was trying this question: 1971F - Circle Perimeter

I saw that I did not pass test 6, so I tried fixing it. Then I figured I can get some help by looking at the test case.

The test case turns out to be simple: 1 100000

So I tested the case on my computer. To my surprise it worked out. The answer was correct!! But the judging server got wrong answer! Now I was raging because I can't get it to pass on the judge so I wrote the same thing in C++. And again surprised me because it actually passed. Now these two are literally the same thing written in two different languages, but why does one work and the other one not? C++: 308206113 PASCAL: 308204979

I did some extra tests. Apparently the sums on my computer and on the judging server don't match. I made a sum that adds up all (mid * mid + x * x). My computer gave me this: 285138544 (which is correct because I verified it with the C++ program that passed), the judge gave me this: -1325314186. (negative probably because of overflow, but if they are the same sum, even the overflowed answer should be the same..) There were no overflows in the process. I tested it by this submission: 308205548 You can see in this submission that the sum was negative: 308205808

So I was wondering how you can have two different results there. It's really weird because addition cannot have two answers...

Is there a problem with the flags the judging servers for pascal is using? Or is it a problem with the PASCAL language? (I don't think it's my problem because my local code's sum matched up with the submission that passed..)

I have seen some similar functions in problems where numbers are large and we need to mod a number like 998244353 or 1000000007 (I also noticed they are all prime). I think this function might be modular inverse??? But I don't know why any of this works and how do I use it. I don't get why I need to decrease 2 from the mod number to make it work. I don't get what the dividing by two is about. Will very appreciate if someone can help. Thank you. +++

1999F - Expected Median

const int N = 2e5 + 5, mod = 1e9 + 7;
int64_t fact[N];
int64_t pw(int64_t a, int64_t b) {
	int64_t r = 1;
	while(b > 0) {
		if(b & 1) r = (r * a) % mod;
		b /= 2;
		a = (a * a) % mod; 
	}
	return r;
}

2053D - Refined Product Optimality

int qpow(int a, int x = MOD — 2) {
	int res = 1;
	for (; x; x >>= 1, a = 1ll * a * a % MOD) if (x & 1) res = 1ll * res * a % MOD;
	return res;
}