DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Cannon

Back to problem

Editorial

Condition within one line Suppose a row has ttt pieces and its leftmost and rightmost occupied columns are L,RL,RL,R.

  • If t≤1t\leq1t≤1, no horizontal capture is possible.
  • If t=2t=2t=2, only empty cells to the left of LLL or right of RRR allow a capture. Between the pieces, neither direction contains two pieces.
  • If t≥3t\geq3t≥3, every empty cell allows a capture: at least one side contains two or more pieces.

The same characterization holds for columns. Store only the count and first and last occupied positions for each row and column.

Count horizontal captures first For each row, add the horizontally valid empty cells: (L−1)+(M−R)(L-1)+(M-R)(L−1)+(M−R) when t=2t=2t=2, or M−tM-t when . Test vertical captures only on the remaining empty intervals:

  • t=0t=0t=0: [1,M][1,M][1,M].
  • t=1t=1t=1: [1,L−1][1,L-1][1, and .

Ignore intervals whose left endpoint exceeds their right endpoint. These intervals never contain occupied cells.

Row sweep with a Fenwick tree Maintain a 111 for each column allowing a vertical capture at the current row, and 000 otherwise. Columns with at most one piece are always 000; columns with at least three pieces are always 111. A column with exactly two pieces in rows U,DU,DU,D has value 11 precisely above or below .

Initialize each two-piece column to 111. Before processing row UUU, change it to 000; before row D+1D+1D+1, change it back to 111. Omit the second event if D=ND=N. A column with at least three pieces may also store at an occupied position, but query intervals exclude every occupied cell.

Sort events by row and sweep downwards. Apply events before querying a row, then add the Fenwick sums of its at most two remaining intervals. Each empty cell allowing a horizontal or vertical capture is counted exactly once.

Complexity and integer bounds There are at most KKK events. Time complexity is O(N+M+Klog⁡(K+1)+Klog⁡(M+1)+Nlog⁡(M+1))O(N+M+K\log(K+1)+K\log(M+1)+N\log(M+1))O(N+M+Klog(K+1; space complexity is . Since , use signed 64-bit integers for the answer and board-area products. Line counts, Fenwick sums, and indices are at most . Generator cell identifiers are below and also fit 64-bit integers.

Subtask 1 scans all cells and directly checks the row and column conditions in O(NM+N+M+K)O(NM+N+M+K)O(NM+N+M+K) time and space, which is sufficient for NM≤10 000NM\leq10\,000NM≤10000. Subtask 2 uses the sweep above.

Solution written by GPT6

M
−
t
t≥3t\geq3t≥3
L
−
1]
[L+1,M][L+1,M][L+1,M]
  • t=2t=2t=2: [L+1,R−1][L+1,R-1][L+1,R−1].
  • t≥3t\geq3t≥3: no intervals remain.
  • 1
    UUU
    DDD
    D=
    N
    111
    )
    +
    Klog(M+
    1)+
    Nlog(M+
    1))
    O(N+M+K)O(N+M+K)O(N+M+K)
    0≤answer≤NM−K<2.5⋅10110\leq\mathrm{answer}\leq NM-K<2.5\cdot10^{11}0≤answer≤NM−K<2.5⋅1011
    500 000500\,000500000
    NMNMNM