The queue stucked.

As we all know, we can write codes like this in C++:

int main() {
    int n;
    cin >> n;
    int a[n];
    ...
}

But when the inputed n is too large, this program will crash.

So,

1. Why it would crash?
2. What is the lowest value n to make it crash?
3. Why using malloc will not cause this problem?

@atcoder_official Please consider add these to Atcoder Library.

• About Trees

1. LCA of two or more vertices
2. Distance of two vertices

• About Graphs

1. Minimum distance (Dijkstra, Johnson, Floyd, SPFA)
2. Tarjan Algorithm

Consider checking $$$k$$$ one by one. Let $$$sq$$$ be $$$\sum_{i=1}^n a_i$$$. For each $$$k \le sq$$$, calculate the strength in $$$O(n)$$$. For the other $$$k$$$, pre-calculate the contribution of $$$c_i \le sq$$$ (their contribution won't change when $$$k > sq$$$). Then we calculate each $$$c_i > sq$$$ (At most $$$sq$$$ occupation of $$$c_i$$$ that $$$c_i > sq$$$). So the total complexity is $$$O(n \cdot sq)$$$.

It gives WA on test 8.

#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
#define int long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;

using ll = __int128;

const int N = 3e5 + 5, M = N << 2, mod = 1000000000000000009LL;
int n, m, q, x[N], v[N], sum[M], mul[M], add[M];
set<pair<int, int>> s;

int inv(int x) {
    if (x == 1) return 1;
    return (ll)(mod - mod / x) * inv(mod % x) % mod;
}

auto findLeft(int p) {
    return prev(s.upper_bound({p, 1e9}));
}

auto findRight(int p) {
    return s.upper_bound({p, 0});
}

int calc(int p) {
    return findLeft(p)->second * (findRight(p)->first - p);
}

void pushup(int p) {
    sum[p] = (sum[ls] + sum[rs]) % mod;
}

void build(int p, int l, int r) {
    // cerr << "build " << p << " " << l << " " << r << endl;
    mul[p] = 1;
    add[p] = 0;
    if (l == r) {
        sum[p] = calc(l);
        return;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(p);
}

void pushdown(int p, int l, int r) {
    // cerr << "pushdown " << p << " " << l << " " << r << endl;
    sum[ls] = ((ll)sum[ls] * mul[p] + (ll)add[p] * (mid - l + 1)) % mod;
    sum[rs] = ((ll)sum[rs] * mul[p] + (ll)add[p] * (r - mid)) % mod;
    mul[ls] = ((ll)mul[ls] * mul[p]) % mod;
    mul[rs] = ((ll)mul[rs] * mul[p]) % mod;
    add[ls] = ((ll)add[ls] * mul[p] + add[p]) % mod;
    add[rs] = ((ll)add[rs] * mul[p] + add[p]) % mod;
    mul[p] = 1;
    add[p] = 0;
}

void update1(int p, int l, int r, int L, int R, int k) {
    // cerr << "update1 " << p << " " << l << " " << r << " " << L << " " << R << " " << k << endl;
    if (L <= l && r <= R) {
        add[p] = (add[p] + k) % mod;
        sum[p] = (sum[p] + k * (r - l + 1)) % mod;
        return;
    }
    pushdown(p, l, r);
    if (L <= mid) update1(ls, l, mid, L, R, k);
    if (R > mid) update1(rs, mid + 1, r, L, R, k);
    pushup(p);
}

void update2(int p, int l, int r, int L, int R, int k) {
    // cerr << "update2 " << p << " " << l << " " << r << " " << L << " " << R << " " << k << endl;
    if (L <= l && r <= R) {
        sum[p] = (ll)sum[p] * k % mod;
        mul[p] = (ll)mul[p] * k % mod;
        add[p] = (ll)add[p] * k % mod;
        return;
    }
    pushdown(p, l, r);
    if (L <= mid) update2(ls, l, mid, L, R, k);
    if (R > mid) update2(rs, mid + 1, r, L, R, k);
    pushup(p);
}

int query(int p, int l, int r, int L, int R) {
    // cerr << "query " << p << " " << l << " " << r << " " << L << " " << R << endl;
    if (L <= l && r <= R) return sum[p];
    pushdown(p, l, r);
    int res = 0;
    if (L <= mid) res = (res + query(ls, l, mid, L, R)) % mod;
    if (R > mid) res = (res + query(rs, mid + 1, r, L, R)) % mod;
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) cin >> x[i];
    for (int i = 1; i <= m; i++) cin >> v[i];
    for (int i = 1; i <= m; i++) s.emplace(x[i], v[i]);
    build(1, 1, n);
    // cerr << "Segment Tree built" << endl;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int nx, nv;
            cin >> nx >> nv;
            pair<int, int> L = *findLeft(nx);
            pair<int, int> R = *findRight(nx);
            // cerr << "L = {" << L.first << ", " << L.second << "}" << endl;
            // cerr << "R = {" << R.first << ", " << R.second << "}" << endl;
            s.emplace(nx, nv);
            update1(1, 1, n, L.first, nx, -L.second * (R.first - nx));
            update2(1, 1, n, nx + 1, R.first, (ll)nv * inv(L.second) % mod);
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << endl;
        }
    }
    return 0;
}

Codeforces finally rolled back the ratings of contest Goodbye 2023. What great news! Congratulations!

Today's Edu round, lots of people were hacked of problem B&C. Most of them got TLE. I think, to avoid this, we should make pretest more strong, or just make the time limit shorter. The writers should think about some wrong solutions that would get TLE and check them if they could pass the pretests. What do you think?

"Conclusion" porblems refer to problems which you may think a lot for a "conclusion" but the codding is very easy. For example, 1919A - Wallet Exchange, 1919B - Plus-Minus Split, 1919C - Grouping Increases, 1919D - 01 Tree and so on.

I am very confused about these problems. Almost always, I'm struggling on one of these problems (maybe C or D or even B in a Div.2 contest). I cannot find such "conclusion" quickly. How can I improve?

I saw this when I tried to post a comment.

You can write no more than 1 comments in 10 minutes

Why use 1 comments here?

It delayed 2 times but it was still full of problems. For example, D is ChatGPTable, G's std was totally wrong and H is OEISable. So, why it remains RATED? Codeforces is able to roll the rating back, why don't do that?

Now polygon.codeforces.com is 502. When will it fixed?

UPD: Now it is fixed, this post is ended.

@MikeMirzayanov

How fast is CF Judgers?

How long will it run a program (in C++) that its time complexity is $$$O(N)$$$ and $$$N = 10^8$$$? What about $$$N = 10^9$$$?

I want to edit my mashups, but I see this:

What happened?

Hello! CodeForces!

The CodeForces's contests always 22:35 to 00:35 (next day), it is not friendly for Chinese or other countries people.

I think CodeForces can change the contest format like USACO, it means that there's a larger windows, but when start the contests, it will only have 2 hours to solve problems.

https://atcoder.jp/contests/abc238/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=mhb2010

https://atcoder.jp/contests/abc240/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=mhb2010

He submit a lot of unuseful code on AtCoder to get TLE. Especially this one:

while(1)cout<<"What a fuck!\nAtcoder is SB!\nTourist is only a rubbish!\nI am IOI AKer!\nABC is shit, ARC is fuck, AGC is just feiwu!\nGutc is god!!!\nThe world is rubbish bin and all people expect me is rubbish!!!!!\n";

He said a lot of bad words.

Can I add somthing on this line?

When will USACO post the result of 2021-2022 December contest?

I couldn't wait for the solution of the contest problem.

Click here to see the Rating Change

By the way, congratulate Sparsely turns to a $$$\color{grey}{\text{Newbie}}$$$!

I try to write Markdown in My problem (On Polygon), but I can only see the text (no Markdown) in preview.

I can't find "Create New Mashup" on the Mashup page.

Friend Link

$$$\Huge{\text{Only For Chinese}}$$$

$$$\Huge{\text{The contest in Codeforces usually is 22:35 to 00:35 (for China). So if we need to attend these contest, we must sleep after 00:35. But we need to go to school next day, so we maybe not pay attention to teachers or sleep at school.}}$$$

$$$\Huge{\text{So, hope the Codeforces contest time starts early(18:00~19:00 is good)!!!!!!}}$$$