Fyind's blog

Intersting facts on scanf/cin,cout and segment tree implementation on C++20(64) and C++17(32)
By Fyind, history, 16 months ago, In English

Problem: 1864F. Exotic Queries

The time limit is 4s. The input size is $$$n,q \le 10^6$$$. The standard solution uses a segment tree and the input/output size is very large. The sync of cin,cout with stdio is turned off in all implementations if cin,cout is used.

Cin,cout vs Fast IO, Scanf on C++20 (64)

  • 220904724 Array implementation with cin,cout on C++20 (64) -> TLE
  • 220952057 Array implementation with Fast IO on C++20 (64) -> 1762 ms
  • 220950571 Array implementation with Scanf on C++20 (64) -> 3181 ms
  • 220950753 Pointer implementation with Scanf on C++20 (64) -> 3868 ms
  • 220947347 Pointer implementation with cin,cout on C++20 (64) -> 1872ms
  • 220954316 Pointer implementation with Fast IO on C++20 (64) -> 2277ms

C++17 (32) vs C++20 (64)

  • 220904724 Array implementation with cin,cout on C++20 (64) -> TLE
  • 220904724 Array implementation with cin,cout on C++17 (32) -> 1621ms
  • 220947347 Pointer implementation with cin,cout on C++20 (64) -> 1872ms
  • 220953695 Pointer implementation with cin,cout on C++17 (32) -> 1934ms

Pointer implementation vs Array implementation

  • 220904724 Array implementation with cin,cout on C++20 (64) -> TLE
  • 220947347 Pointer implementation with cin,cout on C++20 (64) -> 1872ms

Some guessed conclusions

These facts makes no sense to me. Based on the facts, I guess

  • It's better to use Pointer implementation if you use cin,cout on C++20 (64)
  • If you prefer array implementation, use Fast IO or scanf on C++20 (64)
  • The 32/64 bit compiler has some influence on cin,cout performance

Do you guys have some idea why such cases happen? Or did I implement something improper so that it reduced the efficiency?

UPD: Reason of TLE

Thanks areke for pointing out the reason, and related comment and blog.

The thing is, when using cin in a 64-bit compiler, do cin in a separate loop.

Specifically, do

vector<int> vec(n+1);
for (int i = 1;i <= n; ++i) {
    cin >> vec[i];
}
for (int i = 1;i <= n; ++i) {
    pos[vec[i]].push_back(i);
}

instead of 

for (int i = 1;i <= n; ++i) {
    int x; cin >> x;
    pos[x].push_back(i);
}

This modification speeds up the code from TLE to 1216ms !!! 221383761

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

Comments Comments (20)
| Write comment?
»
16 months ago, # |
  Vote: I like it -13 Vote: I do not like it

it's too ?????, use cin/scanf should not influence the effic of array or pointer

→ Reply
»
16 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Today, I noticed same thing.

In this problem on using cin/cout I am getting TLE. But if I use fast I/O i.e. scanf/printf my solution gets accepted.

Accepted code

Getting TLE

Accepted Solution

220982107 TLE 220982253 AC

TLE Code Accepted

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You are not allowed to view the requested page

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your rmq is recursive

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you mean the segment tree part? I think most people would like to use the recursive style of segment tree, so I only tested this style. Indeed, using a bottom-up segment tree (in author's solution) will have lower constant and will be accepted in this case.

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      ... most people would like to use the recursive style ...

      hard to believe it because this approach is faster and shorter

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, this approach is faster and shorter. Emm, I mean, the recursive approach is known to most people. Btw, although I know the bottom-up approach, I still use the recursive one. My reason is that the bottom-up approach is not applicable to lazy propagation in range updates. (Not sure, is it true?)

        → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        I prefer a approach which is easier to understand than faster/shorter code. Ill happily code the slower longer code if i can understand it easily, and not so easily the other one

        → Reply
        • »
          »
          »
          »
          »
          16 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can I then assume that you doesn't use BIT?

          → Reply
          • »
            »
            »
            »
            »
            »
            16 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Actually, yes, well i didnt use to before 2 months ago.

            In our countrys training camp for ioi, one of the people there made me understand how bit works and why the short implementation we write is correct. I have only started using it thereafter.

            → Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Array (actually vectors) and cin worked fine for me.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, thank you for your segment tree implementation and your submission. I only replaced your segment tree implementation in my old submission. Unfortunately, it got TLE. 221057129. Maybe you got accepted because your implementation in other parts is different from mine and somehow has low constant?

    → Reply
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Strange, shouldn't array segtree version be faster than pointers segtree one?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is, and this is main question — why array version on C++20 x64 is TLE

    My guess, that int_fast32_t would work

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      int_fast32_t is just a type synonym, and that fast in it doesn't mean it is fast

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Sure I know it (for C++20 11.2 64x it is just int64_t)

        I mean that in x64 arch massive arithmetic operations on int32_t are not optimal while operations on int64_t are. So for performance one should use it (yes with memory increase, but oh well...)

        221387109

        Update this is difference: 221387456 (int64_t vs int32_t in pos array makes difference)

        → Reply
»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

See this comment.

It's related to https://mirror.codeforces.com/blog/entry/99038.

If you read in the input separately from pushing back to the pos array, the implementation only takes 1216ms: https://mirror.codeforces.com/contest/1864/submission/221383761.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Amazing! This tiny modification can make such a huge difference. Learned something today!

    → Reply