robbers dont know the path, so at each point take farthest node from robbers.do these fo for the length of shortest path and in the end take minimum of these.

for lazy node propagation I did tree[n]+=(end-start+1)*lazy[n];
when start and end were integers. tree[n]+=(end-start+1)*(1ll)*lazy[n]; corrected error.

i got TLE 21

To all of you who cannot overcome #3 !!!

All the suggestions about redundant '\n' and about that the dictionary may have repeated words have nothing to do with WA #3 (read condition carefully).

If you use any kind of backward tracking, be it recursion or DFS, check the "no luck" condition attentively. First i used checking the next letter to be '\0' at the beginning of my recursion function, and if so returned 'true'. This is wrong! You must make word-end check BEFORE you make the next step, otherwise you may get "deadlock" "there is no direction to go" though there is no need to go anymore!!!

Test word for the example table
rabadaabracabrac: YES
(starting from [3,1] in C-like indices).

similar to strictly increasing subsequnce of length k just query and update BIT in reverse.

Clang++ 4.0.1 - 0.39s - Accepted
G++ 7.1 - 0.421 - Accepted
Visual C++ 2017 - 1.029 - Time limit exceeded

rofl

in general i noticed that for the most problems clang is usually faster then g++ or ms c++


Edited by author 21.08.2018 03:53

For WA3 try this:
3
1 2 1
Ans:
1
For WA12 try this:
5 1 2 3 1 5
Ans:
1 5

I had maintained dis[n+1][2] for distance. But visited array was vis[n+1], changed it to
vis[n+1][2] and simple bfs.

I have WA #2 ..

Can somebody give me some tests, please ?:)


Edited by author 13.03.2010 14:57

print(int(input()) % 7)

I can not make tests for which the program gives an incorrect result. Help please

Inspector can come at any point.
  after 1 ball pocketed
  after 2 ball pocketed
  or even at the end when n balls are pocketed
Inspector can collect any number of available balls
e.g if he comes after ball 3 is pocketed he can take just 3, or 3 2 or all 3 2 1

I've been stuck in this problem for a very long time, but today I got the idea of Binary Indexed Tree from wikipedia and finally solved this problem :)
Binary Indexed Tree,or BIT, can be viewed as a simplified version of Segment Tree,easier to code and less function to perform. But It's enough to solve this problem

#include<iostream>
#include<cstdio>
using namespace std;

const int Max = 32005;

int n;
int c[Max] = {0};
int level[Max] = {0};

int lowbit(int x)
{
    return x&(-x);
}

int sum(int i)
{
    int s = 0;
    while(i > 0)
    {
        s += c[i];
        i -= lowbit(i);
    }
    return s;
}

void update(int pos,int val)
{
    while(pos <= Max)
    {
        c[pos] += val;
        pos += lowbit(pos);
    }
}

int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i ++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x ++;
        level[ sum(x) ] ++;
        update(x,1);
    }

    for(int i = 0; i < n; i ++)    printf("%d\n",level[i]);
}

I have two loops which calls recursive function

for 1 to 9
  for 0 to 9
    ans+=f(n-2,j,i) // f(rem,prev,prev_prev)

function f(i,j,k) has dp[1001][10][10] memoized solution.why doesnt it timeout.
I'm having hard time understanding my own solution although it is ACd in one trial.

may be anybody know?

Edited by author 13.09.2016 16:35

Edited by author 13.09.2016 16:35

yes!=YES

Hint: DP on trees
Tutorial Link: https://codeforces.com/blog/entry/20935

Test 01: 10 15  15 10  13 14
Ans  01: 25

Test 02: 0 5  5 0  1 1
Ans  02: 36

Test 03: 10 15  13 14  15 10
Ans  03: 100

Test 04: 10 15  13 14  15 10
Ans  04: 100

Test 05: 10 15  13 14  15 10
Ans  05: 100

Test 06: 2 1  1 2  1 1
Ans  06: 4

Test 07: 200 200  200 300  300 200
Ans  07: 17182

Test 08: 300 300  301 301  500 101
Ans  08: 80089

Test 09: 400 400  400 410  700 405
Ans  09: 90600

Test 10: 11 16  14 11  13 14
Ans  10: 15

Test 11: 4 1  1 6  2 2
Ans  11: 20

Test 12: 11 13  14 19  12 16
Ans  12: 18

Test 13: 11 14  14 20  12 18
Ans  13: 24

Test 14: 100 110  110 100  108 106
Ans  14: 100

Test 15: 100 110  90 100  94 108
Ans  15: 100

Test 16:
Ans  16:

Test 17:
Ans  17:

Test 18:
Ans  18:

Test 19:
Ans  19:

Test 20:
Ans  20:

Test 21:
Ans  21:

Test 22:
Ans  22:

Test 23:
Ans  23:

Test 24:
Ans  24:

Test 25:
Ans  25:

Test 26:
Ans  26:

Test 27:
Ans  27:

Test 28:
Ans  28:

Test 29:
Ans  29:

Test 30:
Ans  30:

Test 31:
Ans  31:

Test 32:
Ans  32:

Test 33: 1 -1000  -1 -1000  999 0
Ans  33: 3998000

Test 34:
Ans  34:

Test 35: 1 1  11 -1  2 0
Ans  35: 30

Test 36: -200 100  -300 -200  -195 -2
Ans  36: 32400

Test 37: -10 -5  -5 -10  -5 -100
Ans  37: 18496