oj.uz

Submission #243583

# Submission time Handle Problem Language Result Execution time Memory
243583 2020-07-01T11:02:12 Z ne4eHbKa Meksikanac (COCI16_meksikanac) C++17
0 / 160
 288 ms 668 KB 
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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Incorrect 5 ms 384 KB Output isn't correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 504 KB Output isn't correct

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 592 KB Output isn't correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 191 ms 632 KB Output isn't correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 556 KB Output isn't correct

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 604 KB Output isn't correct

Subtask #16
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 288 ms 668 KB Output isn't correct