I'm training on Lightoj. And I have trouble in post: https://lightoj.com/problem/politeness. Can anyone give me an idea to solve this problem?

# | User | Rating |
---|---|---|

1 | tourist | 3821 |

2 | Benq | 3744 |

3 | ksun48 | 3559 |

4 | Radewoosh | 3538 |

5 | peehs_moorhsum | 3531 |

6 | Um_nik | 3488 |

7 | maroonrk | 3423 |

8 | Petr | 3379 |

9 | sunset | 3337 |

10 | ecnerwala | 3335 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 206 |

2 | awoo | 181 |

2 | Errichto | 181 |

4 | Um_nik | 180 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 173 |

8 | tourist | 172 |

9 | SecondThread | 171 |

10 | rng_58 | 166 |

When I do an exercise I have a problem that let Ai <= 60 and n <= 1e5 and q <= 1e5, Count number of distinct elements in l to r. With type 1 query update change all elements from l to r to v. Type 2 query answer the number of distinct elements from l to r.

Example:

5 5

1 1 1 1 1

1 2 4 2

1 5 5 3

2 1 5 // is 3.

2 1 4 // is 2.

2 2 4 // is 1.

I know how if we update an element we can do this with the segment tree. But i don't know updating the range. Is this possible? if yes please explain to me. thanks for help!

I just made a mistake while participating in a coding contest in Vietnam and I came across a simple dp problem, the problem was: https://lqdoj.edu.vn/problem/dutpc2a : test of the contest organizers that I participated in, https://atcoder.jp/contests/dp/tasks/dp_h: The problem I encountered is the same as the one on atcoder

But I accepted this problem on atcoder but when I submitted the test from the contest organizer that I joined, I was wrong. And the problem I have is when I compare with the character '.' I got wrong but compare with '#' then accepted. Can someone explain to me why when I compare the character '.' wrong?

**I think there are a few caveats when compared to the '.' and some other special characters, if my thinking is correct, someone can explain it to me.**

this my code wrong:

char v[nax][nax]; int dp[nax][nax];

int32_t main() {

FASTIO int n, m; cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> v[i][j]; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (i == 1 && j == 1) { dp[i][j]=1; } else if (v[i][j] == '.') { dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod; } } } cout << dp[n][m]; return 0;

}

and my code accepted:

char v[nax][nax]; int dp[nax][nax];

int32_t main() {

FASTIO int n, m; cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> v[i][j]; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (i == 1 && j == 1) { dp[i][j]=1; } else { if (v[i][j] != '#') { dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod; } } } } cout << dp[n][m]; return 0;

}

Thanks for the help and sorry for my english!

When learning about 2D BIT, I have the question that 2D BIT can be easily updated 1 element and get sum, but can update the range ?

Problem:

for each query, you need to update the rectangle (x, y, u, v) each coordinate of a rectangle with upper left corner (x, y) and lower right corner being (u, v) incremented by c "at the same time".

After the update, we can find the sum query (x1,y1,x2,y2);

For example:

Sum(2,3,3,4) is 28;

Is it possible to solve this problem? If so, please show how to do it!!!

thanks for help!!!

I just know how to find LCS use dynamic programming:

if (s1 [i] == s2 [j]) dp [i] [j] = dp [i-1] [j-1] +1; else dp [i] [j] = max (dp [i-1] [j], dp [i] [j-1]).

But I have trouble with problem: Find LCS with s1 <= 1e6 and s2 > 1e3. What is the best way to find LCS? Thanks for help!!!

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/28/2021 13:36:12 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|