xcx0902's blog

By xcx0902, history, 12 days ago, In English

In this problem, it said "we partition the elements of ...". Here, the word partition should mean that we can only partition the array without shuffling the order of the elements. For example, you can partition [1,2,3,4,5] to {1,2,3} and {4,5} but not {1,3,4} and {2,5}. However, the editorial showed that you can do the latter one. To tell you i'm not misunderstanding the word "partition", here's the translation of this word with Google Translator:

img

Obviously, the Chinese word "分割" shares the same meaning with what I'm talking above.

Here's the whole translation of the problem.

img

Full text and comments »

  • Vote: I like it
  • -22
  • Vote: I do not like it

By xcx0902, history, 2 months ago, In English

When you tried to submit codes containing something (I cannot even show it here, because it will still be blocked, but it is the string that is the output of the program i'll give in the end of this blog), it redirects you to a Cloudflare page which says that you have been blocked.

MikeMirzayanov Please check this.

The code that will output the banned substring:

// Lang: C11
main() {
printf("c");
printf("=");
printf("c");
printf("h");
printf("a");
printf("r");
printf("(");
printf("\'");
printf("a");
printf("\'");
printf(")");
}

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it

By xcx0902, history, 4 months ago, In English
JUDGER_QUEUE cf_judgers(MAX_SPEED);
cf_judgers.startup(IMMEDIATELY);
cf_judgers.judge_all(IMMEDIATELY);
Spoiler

Full text and comments »

  • Vote: I like it
  • -12
  • Vote: I do not like it

By xcx0902, history, 7 months ago, In English

The queue stucked.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By xcx0902, history, 7 months ago, In English

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?

Full text and comments »

Tags vla
  • Vote: I like it
  • 0
  • Vote: I do not like it

By xcx0902, history, 8 months ago, In English

@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

Full text and comments »

  • Vote: I like it
  • +19
  • Vote: I do not like it

By xcx0902, history, 9 months ago, In English

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)$$$.

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it

By xcx0902, history, 9 months ago, In English

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;
}

Full text and comments »

  • Vote: I like it
  • -13
  • Vote: I do not like it

By xcx0902, history, 9 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • -28
  • Vote: I do not like it

By xcx0902, history, 9 months ago, In English

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?

Full text and comments »

  • Vote: I like it
  • -44
  • Vote: I do not like it

By xcx0902, history, 10 months ago, In English

"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?

Spoiler

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By xcx0902, history, 10 months ago, In English

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?

Full text and comments »

  • Vote: I like it
  • -33
  • Vote: I do not like it

By xcx0902, history, 10 months ago, In English

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?

Full text and comments »

  • Vote: I like it
  • -47
  • Vote: I do not like it

By xcx0902, history, 2 years ago, In English

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

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

@MikeMirzayanov

Spoiler

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it

By xcx0902, history, 2 years ago, In English

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$$$?

Full text and comments »

  • Vote: I like it
  • -12
  • Vote: I do not like it

By xcx0902, history, 2 years ago, In English

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

What happened?

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it

By xcx0902, history, 3 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • -29
  • Vote: I do not like it

By xcx0902, history, 3 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it

By xcx0902, history, 3 years ago, In English

Can I add somthing on this line?

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it

By xcx0902, history, 3 years ago, In English

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

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

Full text and comments »

  • Vote: I like it
  • +28
  • Vote: I do not like it

By xcx0902, history, 3 years ago, In English

Click here to see the Rating Change

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

Full text and comments »

  • Vote: I like it
  • -54
  • Vote: I do not like it

By xcx0902, history, 3 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • -28
  • Vote: I do not like it

By xcx0902, history, 3 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • -21
  • Vote: I do not like it

By xcx0902, history, 3 years ago, In English

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)!!!!!!}}$$$

Full text and comments »

  • Vote: I like it
  • -78
  • Vote: I do not like it