I tried to code the idea that is in the editorial. It doesn't pass 14th test, but I can't find it why. I would appreciate any help. Thank you !
UPD:
I've used the code in this blog for calculating the f array, and I haven't changed any other parts of my code. It worked. Then I tried the idea using my monotonic queue class, which I've written before(and I know that that code is correct because I use it to calculate also g array), and it can't pass the 6th test right now. Where is the difference?
Accepted: 9080710
Wrong Answer: 9084717
I don't really understand why everyone has downvoted. Thank you anyways.
It's rather hard to spot the problem with your code since the it's too long. I believe that's why most have downvoted your post instead of trying to help you somehow. Anyways, this is by far the best tutorial I could've found so far on this problem: http://abitofcs.blogspot.com/2014/11/codeforces-round-278-div1-problem-b.html. It's a lot better than the actual editorial. I hope that will help you figure out what's wrong with your code :)
Thank you :)
Your code does not compile. I took your latest submission, and it gives the following warnings:
x.cpp: In member function 'void Sliding_window::push(int)': x.cpp:113:65: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion] while (!window.empty() and comp(val, window.back().first)) ^ x.cpp: In member function 'int Sliding_window::query()': x.cpp:125:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion] return window.front().first; ^ x.cpp: In function 'int main()': x.cpp:169:31: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion] min_v.push(ar[ind]); ^ x.cpp:170:31: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion] max_v.push(ar[ind]); ^You should fix these warnings first, maybe this is the mistake.
Using long long wasn't really necessary (It was written that way there, so I had changed it to long long from int to see if it was the mistake); therefore, it isn't the problem, but I changed long long to int anyway because using long long is silly.