zeyd1234's blog

By zeyd1234, 2 months ago, translation, In English

Hi Codeforces.

Today I came across a legendary problem: 896E - Welcome home, Chtholly. It’s rated $$$3100$$$ and is known for being a nightmare for data structure enthusiasts. The tags say "DSU" and "Data Structures," and the intended solutions involve complex Sqrt-decomposition or Segment Tree Beats.

But as my future handle suggests -- $$$SegTreeIsAMyth$$$. I decided to see if a simple $$$O(N \cdot M)$$$ brute force could pass.

To my surprise, it didn't just pass: it $$$crushed$$$ the tests in $$$1750ms$$$ (with a 3s limit)!

Screenshot:

The Code

The core of my solution is just a simple loop. No complex trees, no heavy pointers.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define debug cout << "Debug\n"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

/*
      ---===ASCII help===---
     '0' -> 48     '9' -> 57
     'A' -> 65     'Z' -> 90
     'a' -> 97     'z' -> 122
*/

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; cin >> n >> m;
    int arr[n];
    for (int i = 0; i < n; ++i) cin >> arr[i];
    while (m--) {
        int t, l, r, x; cin >> t >> l >> r >> x;
        --l; --r;
        if (t == 1) {
            for (int i = l; i <= r; ++i) {
                if (arr[i] > x) arr[i] -= x;
            }
        }
        else {
            ll ans = 0;
            for (int i = l; i <= r; ++i) {
                if (arr[i] == x) ++ans;
            }
            cout << ans << '\n';
        }
    }
}

Why did it pass?

Many of you might think $$$10^{10}$$$ operations shouldn't pass in 3 seconds. Here is why it did:

  • GCC 14 & AVX2: The #pragma GCC target("avx2") allows the compiler to use SIMD instructions. It processes multiple integers in a single CPU cycle.

  • Loop Unrolling: #pragma GCC optimize("unroll-loops") reduces the overhead of the loop control.

  • Cache Locality: A simple array traversal is the most cache-friendly operation possible. While a Segment Tree jumps around in memory causing cache misses, the CPU prefetcher loves this linear scan.

  • Modern Judges: Codeforces' upgraded hardware is incredibly fast at executing vectorized code.

Conclusion

Next time you see a 3100-rated problem, don't be afraid. Sometimes, the "dumb" solution with the right pragmas is more powerful than the most sophisticated data structure.

Is Segment Tree actually a myth? My submission says yes.

UPD: Bruh, -16. Maybe SegTree lovers hates me.

UPD 2: My contribution is dropping faster than the array values in the problem. Mission accomplished: SegTree lovers are officially summoned!

Full text and comments »

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

By zeyd1234, 4 months ago, translation, In English

Hello again. Thank you for participating. I hope that you liked the problems. Sorry for the mistakes in constraints and statement. In other rounds, i will check all tasks twice, to don't allow that mistakes. There is an Editorial:

A — Petya and Car Counting

Solution
Implementation

B1 — Armstrong Numbers Count

Solution
Implementation

B2 — Armstrong Numbers Count(Harder Version)

Solution
Implementation

C — Active Users in Chat

Solution
Implementation

Full text and comments »

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

By zeyd1234, 4 months ago, In English

Hello everyone. I invite you to the Amateur Round 1 (Div. 4), which already started in 07.01.2026 and ends in 15.01.2026.

You will be given 4 problems to solve. One problem will be divided into subtasks. The round will be in ICPC style.

The problems authored by zeyd1234.

I want to say "Thank you" to:

  • You for participating.

Note:

If you are using Python, use sys.stdin.readline() instead of input() to prevent EOFError.

UPD: Editorial is out.

UPD2: Congratulations to the top — 10 winners:

Rules
  1. krishnsai324
  2. goririn
  3. jowelo
  4. C99_x
  5. Light_Bender
  6. Ajay967
  7. mathc
  8. Senpai_
  9. TruthSeekerGT
  10. UkashaUKPower

And congratulations to top — 15 by official standing:

  1. PhirainEX
  2. ink65536
  3. reirugan
  4. krishnsai324
  5. potatoArmy
  6. Mitpro
  7. Furioso_Slient
  8. salemi1
  9. goririn
  10. Jim_X
  11. jowelo
  12. C99_x
  13. fatespeaker
  14. OAY71011
  15. Light_Bender

And this is a top — 10 by only WA penalty count:

  1. reirugan
  2. goririn
  3. OAY71011
  4. Zaid_804
  5. KaiLearningCP
  6. MisterGir
  7. cy171
  8. wtf.rjdp1
  9. sahaun
  10. raafael

Full text and comments »

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