oj.uz

Submission #251336

# Submission time Handle Problem Language Result Execution time Memory
251336 2020-07-20T20:42:20 Z VEGAnn Meksikanac (COCI16_meksikanac) C++14
160 / 160
 296 ms 8952 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
#define ft first
#define sd second
#define i2 pair<int,int>
#define i4 pair<i2,i2>
using namespace std;
typedef long double ld;
const int root = 31;
const int md = 998244353;
const int oo = 2e9;
const int MX = 510;
const int N = MX * MX; // 255k (?)
const int K = 10010;
const ld E = 1e-9;
const int PW = 24;
vector<int> flies, poly, res;
vector<i4> seg;
int xf[N], yf[N], xp[K], yp[K], xb, yb, n, k, ans, roots[PW];
bool inside[MX][MX];

void BAD(){
    cout << 0;
    exit(0);
}

ld get_cord(i4 fi, ld cr_x){
    return ld(fi.ft.sd) + (ld)(fi.sd.sd - fi.ft.sd) * (ld)(cr_x - fi.ft.ft) / (ld)(fi.sd.ft - fi.ft.ft);
}

int area(i2 p1, i2 p2, i2 p3){
    return (p2.ft - p1.ft) * (p3.sd - p1.sd) - (p2.sd - p1.sd) * (p3.ft - p1.ft);
}

struct cmp{
    bool operator()(const i4 &fi, const i4 &se) const {
        if (fi.ft == se.ft){
            return area(fi.sd, fi.ft, se.sd) < 0;
        } else if (fi.sd == se.sd){
            return area(fi.ft, fi.sd, se.ft) > 0;
        } else {
            ld cr_x = max(fi.ft.ft, se.ft.ft);

            ld y_fi = get_cord(fi, cr_x);
            ld y_se = get_cord(se, cr_x);

            return y_fi < y_se;
        }
    }
};

set<i4, cmp> events;
set<i4, cmp>::iterator iter;

void get_points(){
    int mx = oo, my = oo;

    for (int i = 0; i < k; i++){
        mx = min(mx, xp[i]);
        my = min(my, yp[i]);
    }

    for (int i = 0; i < k; i++){
        xp[i] -= mx;
        yp[i] -= my;

        if (xp[i] > xb || yp[i] > yb)
            BAD();

        inside[xp[i]][yp[i]] = 1;
    }

    for (int i = 0; i < k; i++){
        int nt = (i + 1) % k;

        if (xp[i] == xp[nt]){
            int fr = min(yp[i], yp[nt]);
            int to = max(yp[i], yp[nt]);

            for (int j = fr; j <= to; j++)
                inside[xp[i]][j] = 1;
        } else {
            seg.PB({{xp[i], yp[i]}, {xp[nt], yp[nt]}});

            seg.PB({{xp[nt], yp[nt]}, {xp[i], yp[i]}});
        }
    }

    sort(all(seg));

    for (int x_cr = 0, id = 0; x_cr <= xb; x_cr++){
        int j = id;

        while (j < sz(seg) && seg[j].ft.ft == x_cr){
            if (seg[j].ft < seg[j].sd)
                events.insert(seg[j]);
            else {
                swap(seg[j].ft, seg[j].sd);
                events.erase(seg[j]);
            }

            j++;
        }

        if (sz(events) > 0){
            iter = events.begin();

            ld cord = get_cord(*iter, x_cr);

            int par = 1;

            for (iter = next(iter); iter != events.end(); iter = next(iter), par ^= 1) {
                ld nw_cd = get_cord(*iter, x_cr);

                if (par){
                    int fr = (int)ceil(cord - E);
                    int to = (int)trunc(nw_cd + E);

                    for (int it = fr; it <= to; it++)
                        inside[x_cr][it] = 1;
                }

                cord = nw_cd;
            }
        }

        id = j;
    }
}

int mult(int x, int y) { return (1ll * x * y) % md; }

int sum(int x, int y){
    x += y;
    if (x >= md)
        x -= md;
    return x;
}

int binpow(int x, int po){
    int res = 1;
    while (po > 0){
        if (po & 1)
            res = mult(res, x);
        x = mult(x, x);
        po >>= 1;
    }
    return res;
}

void fft(vector<int> &a, int po){
    if (po == 0) return;

    int siz = (1 << po);
    int hlf = (siz >> 1);

    vector<int> a0(hlf), a1(hlf);

    for (int i = 0, j = 0; i < siz; i += 2, j++){
        a0[j] = a[i];
        a1[j] = a[i + 1];
    }

    fft(a0, po - 1);
    fft(a1, po - 1);

    int fi = 1, se = roots[1];

    for (int i = 0; i < hlf; i++){
        a[i] = sum(a0[i], mult(a1[i], fi));
        a[i + hlf] = sum(a0[i], mult(a1[i], se));

        fi = mult(fi, roots[po]);
        se = mult(se, roots[po]);
    }
}

vector<int> multiply(vector<int> &a, vector<int> &b){
    int po = 0;

    while (max(sz(a), sz(b)) >= (1 << (po + 1)))
        po++;

    po++;

    while (sz(a) < (1 << po)) a.PB(0);
    while (sz(b) < (1 << po)) b.PB(0);

    fft(a, po);
    fft(b, po);

    for (int i = 0; i < sz(a); i++)
        a[i] = mult(a[i], b[i]);

    fft(a, po);

    reverse(a.begin() + 1, a.end());

    int inv = binpow(sz(a), md - 2);

    for (int i = 0; i < sz(a); i++)
        a[i] = mult(a[i], inv);

    return a;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    roots[PW - 1] = root;

    for (int po = PW - 2; po >= 0; po--)
        roots[po] = mult(roots[po + 1], roots[po + 1]);

    cin >> xb >> yb >> n;

    for (int i = 0; i < n; i++)
        cin >> xf[i] >> yf[i];

    cin >> k;

    for (int i = 0; i < k; i++)
        cin >> xp[i] >> yp[i];

    get_points();

    int mem_x = (1 + yb) * 2, mem_wh = mem_x * (xb + 1);
    int Mx = -oo, My = -oo;

    for (int i = 0; i < k; i++){
        Mx = max(Mx, xp[i]);
        My = max(My, yp[i]);
    }

    flies.resize(mem_wh);
    poly.resize(mem_wh);

    for (int x = 0; x <= xb; x++)
    for (int y = 0; y <= yb; y++)
        if (inside[x][y])
            poly[x * mem_x + y] = 1;

    for (int i = 0; i < n; i++)
        flies[mem_wh - 1 - (xf[i] * mem_x + yf[i])] = 1;

    res = multiply(flies, poly);

    for (int x = 0; x <= xb; x++)
    for (int y = 0; y <= yb; y++)
        if (res[mem_wh - 1 - (x * mem_x + y)] == 0 && x + Mx <= xb && y + My <= yb)
            ans++;

    cout << ans;

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 9 ms 768 KB Output is correct
3 Correct 10 ms 640 KB Output is correct
4 Correct 14 ms 640 KB Output is correct
5 Correct 11 ms 768 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 18 ms 896 KB Output is correct
3 Correct 17 ms 896 KB Output is correct
4 Correct 17 ms 896 KB Output is correct
5 Correct 18 ms 896 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 18 ms 1000 KB Output is correct
3 Correct 17 ms 1000 KB Output is correct
4 Correct 16 ms 996 KB Output is correct
5 Correct 17 ms 908 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 17 ms 1000 KB Output is correct
3 Correct 17 ms 1000 KB Output is correct
4 Correct 18 ms 1000 KB Output is correct
5 Correct 17 ms 872 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 2720 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 8944 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 8952 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2576 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 4668 KB Output is correct

Subtask #16
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 8880 KB Output is correct