### Fyind's blog

By Fyind, history, 3 months ago,

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

• +42

 » 3 months ago, # |   -13 it's too ?????, use cin/scanf should not influence the effic of array or pointer
»
3 months ago, # |
Rev. 3   0

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

•  » » 3 months ago, # ^ |   +5 You are not allowed to view the requested page
•  » » » 3 months ago, # ^ |   0 Updated. I solved this problem in codeforces gym and it doesn't allow to view others solution until you solve it. So is there any way to make it public. I have pasted my code on pastbin and given links in above comment.
 » 3 months ago, # |   0 Your rmq is recursive
•  » » 3 months ago, # ^ |   0 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.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 ... most people would like to use the recursive style ...hard to believe it because this approach is faster and shorter
•  » » » » 3 months ago, # ^ |   0 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?)
•  » » » » » 3 months ago, # ^ |   +3 there is bottom-up approach, see atcoder library
•  » » » » » » 3 months ago, # ^ |   0 I see, thanks for sharing the link
•  » » » » 3 months ago, # ^ |   +10 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
•  » » » » » 3 months ago, # ^ |   0 Can I then assume that you doesn't use BIT?
•  » » » » » » 3 months ago, # ^ |   0 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.
 » 3 months ago, # | ← Rev. 2 →   0 Array (actually vectors) and cin worked fine for me.
•  » » 3 months ago, # ^ |   0 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?
 » 3 months ago, # |   +5 Strange, shouldn't array segtree version be faster than pointers segtree one?
•  » » 3 months ago, # ^ |   0 It is, and this is main question — why array version on C++20 x64 is TLEMy guess, that int_fast32_t would work
•  » » » 3 months ago, # ^ |   0 int_fast32_t is just a type synonym, and that fast in it doesn't mean it is fast
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 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...)221387109Update this is difference: 221387456 (int64_t vs int32_t in pos array makes difference)
 » 3 months ago, # |   +4 See this comment.It's related to https://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://codeforces.com/contest/1864/submission/221383761.
•  » » 3 months ago, # ^ |   0 Amazing! This tiny modification can make such a huge difference. Learned something today!
 » 3 months ago, # |   0 Great!