Submission #288285

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
288285	2020-09-01 11:36:32	rama_pang	Abduction 2 (JOI17_abduction2)	C++14	100 / 100	656 ms	5372 KiB

abduction2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
// Speed up looking next line change with sparse table,
// and memoize based on [left_end, right_end] of each
// street. State is O(H + W), since for every line x and
// the section we enter it, and from that line we go left
// or right to change to another line y and z, then if we 
// change the path and instead goes through a line that passes
// through y and z, we will never stop at x. Thus for each
// line only one "region" matters.
// Time: O(Q * (H + W))
using lint = long long;
const int MAXN = 100005;
int H, W, Q;
array<int, 3> A[MAXN];
int st[MAXN];
int et[MAXN];
lint dpl[MAXN];
lint dpr[MAXN];
int revpos[MAXN][2];
lint Solve(int X, int Y, int mask) {
  lint res = 0;
  int xl = 0, xr = H - 1;
  int yl = 0, yr = W - 1;
  memset(dpl, 0, sizeof(dpl));
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 56 / 56