determinism's blog

Strip — Monotonic Queue
By determinism, 11 years ago, In English

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

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

»
11 years ago, hide # |
← Rev. 4  
Vote: I like it +5 Vote: I do not like it

I don't really understand why everyone has downvoted. Thank you anyways.

→ Reply
»
11 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

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 :)

→ Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

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

    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.

    → Reply