こういうセット辛すぎないか?
AB
はい
C
ちょっと詰まるよね。とりあえずjを固定して雑に数えて引くんだけど、引く時はしゃくとりが使えます。
D
累積和やるだけ。全然綺麗な方法思いつかなかった…。imos法もバグらせまくった…
ll H, W; int N, M; int B[2010][2010]; int D[2010][2010]; int XA[2010]; int YA[2010]; void solve() { cin >> H >> W; cin >> N >> M; rep(i, 0, N) { string str; cin >> str; rep(j, 0, M) { if(str[j] == '#') B[i][j] = 1; } } bool found = false; rep(x, 0, N) { rep(y, 0, M) { if(B[x][y]) { found = true; ll x2 = x + min(H - N, (ll)N), y2 = y + min(W - M, (ll)M); if(H - N + 1 > N + 1) { //xhamidasu XA[y + 1]++; XA[y2 + 2]--; } if(W - M + 1 > M + 1) { //yhamidasu YA[x + 1]++; YA[x2 + 2]--; } D[x + 1][y + 1]++; D[x2 + 2][y2 + 2]++; D[x + 1][y2 + 2]--; D[x2 + 2][y + 1]--; } } } if(!found) { cout << 0 << "\n"; return; } else { ll res = 0; rep(x, 0, 2 * N) { rep(y, 0, 2 * M) { D[x + 1][y + 1] += D[x + 1][y] + D[x][y + 1] - D[x][y]; res += (D[x + 1][y + 1] > 0); } } rep(y, 0, 2 * M) { XA[y + 1] += XA[y]; res += (XA[y + 1] > 0) * max(H - 2 * N, 0ll); } rep(x, 0, 2 * N) { YA[x + 1] += YA[x]; res += (YA[x + 1] > 0) * max(W - 2 * M, 0ll); } res += 1ll * max(W - 2 * M, 0ll) * max(H - 2 * N, 0ll); cout << res << "\n"; } }
E
multisetやるだけ。これもめんどくさい…
ll Y, W, D; int N, M; ll A[110]; map<ll, int> S; vl vec[MAX_N]; ll res; ll bet(ll nd, ll d) { if(1 <= d - nd - 1 && d - nd - 1 <= D) { return d - nd - 1; } else return 0; } void del(ll d, ll e) { // S is bigger than 1 S[d]--; if(S[d] == 0) { auto at = S.lower_bound(d); if(at == (--S.end())) { auto p = at; p--; res -= bet(p->fst, at->fst); } else if(at == S.begin()) { auto p = at; p++; res -= bet(at->fst, p->fst); } else { auto pp = at, np = at; pp--; np++; if(bet(pp->fst, np->fst) == 0) { res -= bet(pp->fst, at->fst); res -= bet(at->fst, np->fst); } else res++; } S.erase(d); res--; } d += e; S[d]++; if(S[d] == 1) { auto at = S.lower_bound(d); if(at == (--S.end())) { auto p = at; p--; res += bet(p->fst, at->fst); } else if(at == S.begin()) { auto p = at; p++; res += bet(at->fst, p->fst); } else { auto pp = at, np = at; pp--; np++; if(bet(pp->fst, np->fst) == 0) { res += bet(pp->fst, at->fst); res += bet(at->fst, np->fst); } else res--; } res++; } } void solve() { cin >> Y >> W; cin >> N >> M >> D; rep(i, 0, N) { cin >> A[i]; A[i]--; S[A[i]]++; } rep(i, 0, M) { ll a, b; cin >> a >> b; a--; b--; S[a * W + b]++; vec[b].pb(a * W + b); } if(N + M <= 1) { rep(i, 0, W) cout << N + M << "\n"; return; } res = sz(S); ll prev = -linf; for(pl a : S) { res += bet(prev, a.fst); prev = a.fst; } rep(i, 0, W) { cout << res << "\n"; rep(j, 0, N) { del(A[j]++, 1); } rep(j, 0, sz(vec[i])) { del(vec[i][j], W); } } }
こういうコンテストで勝てるようになったらすごい強くなれそうだけどなぁ。
