Scoring distribution looks friendly! I'll surely participate. GLHF!

C++20 support when

Good luck! Scoring distribution DOES look friendly! Wish everyone's rating increases!

Great problem D, awesome generalization of the classic LIS (and hence a very natural problem statement).

Got TLE again and again on B problem (36/41). This 2sec time limit sucks :(
Can someone tell me how I can optimize this further..

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

long long A, B;
scanf("%lld %lld", &A, &B);
long long g = std::__gcd(A, B);

long long n = 0;
while (A >= 1 && B >= 1) {
    A -= g;
    B -= g;
    std::swap(A, B);
    g = std::__gcd(A, B);
    ++n;
}

if (A == 0 || B == 0) 
    printf("%lld", n) ;
else 
    printf("%lld", n-1) ;

can anyone explain how to solve B? The editorial is slightly confusing.

Another round with 3200perf+unr_reg

Why my D code always Runtime Error and Wrong Answer? Can anyone help me? Code Link

Actually, we can find the minimum number of operations required for problem C (code). Though it was much harder to implement than simply constructing one, and I couldn't manage to finish it during contest time :(

Can anyone explain the O(n) solution of the F problem (official editorial)? Even though I've gotten AC, I still can't understand the official editorial.

For D what should be the solution for this input?

1 1, 2 7, 4 7, 10 15

An Accepted solution return the result = 11. But I think the solution is 13 is it not? Writing this out I get X = 1, 2, 3, 4, 5, 6, 7, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15 It seems plain to me that I would take 1,2,3,4,5,6,7,10,11,12,13,14,15 as the longest strictly increasing subsequence?

Maybe I found a missing testcase actually cause If I try

1 1, 2 7, 4 8, 10 15

The same accepted solution gives 14, which is the answer I would expect for this.

This is the solution that seems to give these, It was written from someone else I was just learning it, and realized it didn't make sense on a test input I came up with.

class SegmentTree():
    """UnitXは単位元、fは区間で行いたい操作、initは自然数あるいは配列"""
    def __init__(self, init, unitX, f):
        self.f = f # (X, X) -> X
        self.unitX = unitX
        self.f = f
        if type(init) == int:
            self.n = init
            self.n = 1 << (self.n &mdash; 1).bit_length()
            self.X = [unitX] * (self.n * 2)
        else:
            self.n = len(init)
            self.n = 1 << (self.n &mdash; 1).bit_length()
            # len(init)が2の累乗ではない時UnitXで埋める
            self.X = [unitX] * self.n + init + [unitX] * (self.n &mdash; len(init))
            # 配列のindex1まで埋める
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
    
    def update(self, i, x):
        """0-indexedのi番目の値をxで置換"""
        # 最下段に移動
        i += self.n
        self.X[i] = x
        # 上向に更新
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
            i >>= 1
    
    def getvalue(self, i):
        """元の配列のindexの値を見る"""
        return self.X[i + self.n]
    
    def getrange(self, l, r):
        """区間[l, r)でのfを行った値"""
        l += self.n
        r += self.n
        al = self.unitX
        ar = self.unitX
        while l < r:
            # 左端が右子ノードであれば
            if l & 1:
                al = self.f(al, self.X[l])
                l += 1
            # 右端が右子ノードであれば
            if r & 1:
                r -= 1
                ar = self.f(self.X[r], ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)
 
R = []
Q = []
N = 4
arr = [(1, 1), (2, 7), (4, 7), (10, 15)]
for l, r in arr:
    R.append(r)
    R.append(l)
    Q.append([l,r])
dic = {num:i for i, num in enumerate(list(sorted(set(R))))}
st1 = SegmentTree([0]*len(dic),-float('inf'),max)
st2 = SegmentTree([-float('inf')]*len(dic),-float('inf'),max)
res = 0
for l,r in Q:
    nn = r-l+1
    m1 = st1.getrange(0,dic[l])
    m2 = st2.getrange(dic[l],dic[r])
    nn = max(nn,m1+r-l+1,m2+r)
    st1.update(dic[r],nn)
    st2.update(dic[r],nn-r)
    res = max(res,nn)
print(res)