Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[競プロ典型90問] 010 - Score Sum Queries（★2） #6

Open
shimopino opened this issue Sep 4, 2021 · 1 comment
Open

[競プロ典型90問] 010 - Score Sum Queries（★2） #6

shimopino opened this issue Sep 4, 2021 · 1 comment
Labels
灰diff 競プロ典型90問 累積和

Comments

@shimopino
Copy link
Owner

shimopino commented Sep 4, 2021 •
edited
Loading

リンク

着想

  • 全探索は計算量的に厳しそう
    • 生徒の数: N
    • 質問の数: Q
    • 単純にループで計算すると最低でも O(NQ) となる
    • 制約から O(NQ) は 10^10 となってしまい TLE になってしまう
  • 解決策
    • 累積和を使用する
      • 事前計算: O(N)
      • クエリ計算: O(Q)
      • 合計で O(N + Q) であり十分計算できる

公式回答も一緒であった。

image

ACコード

その他

  • 類題はコメントに追加する
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
灰diff 競プロ典型90問 累積和
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@shimopino