Appy Loves One

All submissions for this problem are available.
###Read problems statements [Hindi](http://www.codechef.com/download/translated/NOV18/hindi/HMAPPY1.pdf) , [Vietnamese](http://www.codechef.com/download/translated/NOV18/vietnamese/HMAPPY1.pdf) , [Mandarin Chinese](http://www.codechef.com/download/translated/NOV18/mandarin/HMAPPY1.pdf) , [Russian](http://www.codechef.com/download/translated/NOV18/russian/HMAPPY1.pdf) and [Bengali](http://www.codechef.com/download/translated/NOV18/bengali/HMAPPY1.pdf) as well. Chef has a sequence $A_1, A_2, \ldots, A_N$; each element of this sequence is either $0$ or $1$. Appy gave him a string $S$ with length $Q$ describing a sequence of queries. There are two types of queries:  '!': rightshift the sequence $A$, i.e. replace $A$ by another sequence $B_1, B_2, \ldots, B_N$ satisfying $B_{i+1} = A_i$ for each valid $i$ and $B_1 = A_N$  '?': find the length of the longest contiguous subsequence of $A$ with length $\le K$ such that each element of this subsequence is equal to $1$ Answer all queries of the second type. ### Input  The first line of the input contains three spaceseparated integers $N$, $Q$ and $K$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$.  The third line contains a string with length $Q$ describing queries. Each character of this string is either '?', denoting a query of the second type, or '!', denoting a query of the first type. ### Output For each query of the second type, print a single line containing one integer — the length of the longest required subsequence. ### Constraints  $1 \le K \le N \le 10^5$  $1 \le Q \le 3 \cdot 10^5$  $0 \le A_i \le 1$ for each valid $i$  $S$ contains only characters '?' and '!' ### Subtasks **Subtask #1 (30 points):**  $1 \le N \le 10^3$  $1 \le Q \le 3 \cdot 10^3$ **Subtask #2 (70 points):** original constraints ### Example Input ``` 5 5 3 1 1 0 1 1 ?!?!? ``` ### Example Output ``` 2 3 3 ``` ### Explanation  In the first query, there are two longest contiguous subsequences containing only $1$s: $A_1, A_2$ and $A_4, A_5$. Each has length $2$.  After the second query, the sequence $A$ is $[1, 1, 1, 0, 1]$.  In the third query, the longest contiguous subsequence containing only $1$s is $A_1, A_2, A_3$.  After the fourth query, $A = [1, 1, 1, 1, 0]$.  In the fifth query, the longest contiguous subsequence containing only $1$s is $A_1, A_2, A_3, A_4$ with length $4$. However, we only want subsequences with lengths $\le K$. One of the longest such subsequences is $A_2, A_3, A_4$, with length $3$.Author:  hmrockstar 
Editorial  https://discuss.codechef.com/problems/HMAPPY1 
Tags  deque, easy, hmrockstar, nov18, segmenttree, taran_1407 
Date Added:  25102018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions