Submission #243583

#	Time	Username	Problem	Language	Result	Execution time	Memory
243583		ne4eHbKa	Meksikanac (COCI16_meksikanac)	C++17	0 / 160	288 ms	668 KiB

meksikanac

using namespace std;
#include <bits/stdc++.h>

#define fo(x) for(int i = 0; i < x; ++i)
#define no return void(cout << "0\n")

template<typename t> void umin(t &a, t b) {a = min(a, b);}
template<typename t> void umax(t &a, t b) {a = max(a, b);}

const int N = 505;
const int K = 10005;
const int oo = 1e9 + 5;

typedef bitset<N> bs;

struct pt {
    int x, y;
    void read() {
        cin >> x >> y;
    }
};

int fh, fw, ph, pw, n, k, mn, mx;
pt f[N * N], p[K];

bs po[N], fl[N];

#define _ <<' '<<

void solve() {
    cin >> fw >> fh >> n;
    fo(n) f[i].read();
    cin >> k;
    fo(k) p[i].read();

    mn = +oo; fo(k) umin(mn, p[i].x); fo(k) p[i].x -= mn;
    mn = +oo; fo(k) umin(mn, p[i].y); fo(k) p[i].y -= mn;

    pw = 0; fo(k) umax(pw, p[i].x); if(pw > fw) no;
    ph = 0; fo(k) umax(ph, p[i].y); if(ph > fh) no;

    fo(fw + 1) fl[i].reset();
    fo(n) fl[f[i].x].set(f[i].y);

    for(int x = 0; x <= pw; ++x) {
        po[x].reset();
        set<int> v;
        fo(k) {
            pt &a = p[i], &b = p[(i + 1) % k];
            int lx = a.x, ly = a.y, rx = b.x, ry = b.y;
            if(lx > rx) swap(lx, rx), swap(ly, ry);
            if(lx > x || rx < x) continue;
            if(lx == rx) {
                for(int y = ly; y <= ry; ++y) po[x].set(y);
                continue;
            }
            int d = ly + ((ry - ly) * (x - lx) + rx - lx - 1) / (rx - lx);
            if(v.count(d)) v.erase(d); else v.insert(d);
        }
        int z = 0; auto it = v.begin();
        for(int y = 0; y <= ph; ++y) {
            bool u = false;
            for(; it != v.end() && *it <= y; ++it) {
                z ^= 1;
                if(*it == y) u = true;
            }
            if(z + u) po[x].set(y);
        }
    }

    int ans = 0;

    for(int x = 0; x <= pw; ++x) {
        for(int y = 0; y <= ph; ++y) cerr << po[x][y];
        cerr << endl;
    }

    for(int dx = 0; pw + dx <= fw; ++dx) {
        for(int dy = 0; ph + dy <= fh; ++dy) {
            for(int x = 0; x <= pw; ++x)
                if((po[x] << dy & fl[x + dx]).any()) goto bad;
            ++ans;
            bad:;
        }
    }

    cout << ans << endl;
}

int main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    for(int i = 1; i <= t; ++i) {
        cerr << "case #" << i << endl;
        solve();
        cerr << endl;
    }
#else
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve();
#endif // _LOCAL
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10
• Subtask 16: 0 / 10