oj.uz

Submission #126020

# Submission time Handle Problem Language Result Execution time Memory
126020 2019-07-06T18:20:02 Z the_art_of_war Pyramid Base (IOI08_pyramid_base) C++14
70 / 100
 5000 ms 60948 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
#define pb push_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define all(a) a.begin(),a.end()
bool debug = 0;
const int MAXN = 1e6 + 100;
const int LOG = 25;
const int mod = 1e9 + 7;
const int MX = 1e6 + 100;
typedef long long li;
const li MOD = 1000000000949747713ll;

#define y1 agasdgaf
int x1[MAXN], x2[MAXN], y1[MAXN], y2[MAXN];

struct event {
    int x;
    int l, r;
    int add;
    int val;

    bool operator<(const event &o) const {
        if (x != o.x)
            return x < o.x;
        if (add != o.add)
            return add == 1;
        return false;
    }
};

ll t[4 * MX];
ll add[4 * MX];
#define left v<<1,tl,tm
#define right v<<1|1,tm+1,tr

void build(int v, int tl, int tr) {
    t[v] = add[v] = 0;
    if (tl == tr) {

    } else {
        int tm = (tl + tr) >> 1;
        build(left);
        build(right);
    }
}

inline void upd(int v) {
    t[v] = min(t[v << 1] + add[v << 1], t[v << 1 | 1] + add[v << 1 | 1]);
}

void update(int v, int tl, int tr, int l, int r, ll val) {
    if (l > tr || r < tl)
        return;
    if (l <= tl && tr <= r) {
        add[v] += val;
        return;
    } else {
        int tm = (tl + tr) >> 1;
        update(left, l, r, val);
        update(right, l, r, val);
        upd(v);
    }
}


inline ll get(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl)
        return inf_ll;
    if (l <= tl && tr <= r) {
        return t[v] + add[v];
    } else {
        int tm = (tl + tr) >> 1;
        ll val1 = get(left, l, r);
        ll val2 = get(right, l, r);
        return add[v] + min(val1, val2);
    }
}

int c[MAXN];


int t2[4 * MX], val2[4 * MX];

void build2(int v, int tl, int tr) {
    t2[v] = val2[v] = 0;
    if (tl == tr) {

    } else {
        int tm = (tl + tr) >> 1;
        build2(left);
        build2(right);
    }
}

inline void upd2(int v) {
    t2[v] = (val2[v] > 0) || (t2[v << 1] && t2[v << 1 | 1]);
}

void update2(int v, int tl, int tr, int l, int r, int x) {
    if (l > tr || r < tl)
        return;
    if (l <= tl && tr <= r) {
        val2[v] += x;
        upd2(v);
        return;
    } else {
        int tm = (tl + tr) >> 1;
        update2(left, l, r, x);
        update2(right, l, r, x);
        upd2(v);
    }
}

bool get2(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl)
        return true;
    if (t2[v])
        return true;
    if (l <= tl && tr <= r) {
        return t2[v];
    } else {
        int tm = (tl + tr) >> 1;
        return get2(left, l, r) && get2(right, l, r);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    ll B;
    cin >> B;
    int k;
    cin >> k;
    for (int i = 1; i <= k; ++i) {
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i] >> c[i];
    }

    int l = 1, r = min(n, m);
    int ans = 0;

    if(B == 0) {
        while (l <= r) {
            int mid = (l + r) >> 1;
            vector<event> cc;
            dout << "mid " << mid << endl;
            for (int i = 1; i <= k; ++i) {
                event e1, e2;
                e1.x = x1[i] - mid + 1;
                e1.l = y1[i] - mid + 1;
                e1.r = y2[i];
                e1.val = 1;
                e1.add = 1;

                dout << e1.x << " " << e1.l << " " << e1.r << " " << e1.val << " " << e1.add << endl;

                e2.x = x2[i];
                e2.l = y1[i] - mid + 1;
                e2.r = y2[i];
                e2.val = -1;
                e2.add = -1;
                cc.pb(e1);
                cc.pb(e2);
            }
            sort(all(cc));
            int top = 0;
            build2(1, 1, m);

            bool flag = false;
            for (int x = 1; x <= n && x + mid - 1 <= n; ++x) {
                while (top < sz(cc) && cc[top].x < x) {
                    update2(1, 1, m, cc[top].l, cc[top].r, cc[top].val);
                    top++;
                }
                while (top < sz(cc) && cc[top].x == x && cc[top].add == 1) {
                    update2(1, 1, m, cc[top].l, cc[top].r, cc[top].val);
                    top++;
                }

                ll val = get2(1, 1, m, 1, m - mid + 1);

                if (val <= B) {
                    flag = true;
                    break;
                }

            }

            if (flag) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }


        }

        cout << ans << "\n";
        return;

    }


    while (l <= r) {
        int mid = (l + r) >> 1;
        vector<event> cc;
        dout << "mid " << mid << endl;
        for (int i = 1; i <= k; ++i) {
            event e1, e2;
            e1.x = x1[i] - mid + 1;
            e1.l = y1[i] - mid + 1;
            e1.r = y2[i];
            e1.val = c[i];
            e1.add = 1;

            dout << e1.x << " " << e1.l << " " << e1.r << " " << e1.val << " " << e1.add << endl;

            e2.x = x2[i];
            e2.l = y1[i] - mid + 1;
            e2.r = y2[i];
            e2.val = -c[i];
            e2.add = -1;
            cc.pb(e1);
            cc.pb(e2);
        }
        sort(all(cc));
        int top = 0;
        build(1, 1, m);

        bool flag = false;
        for (int x = 1; x <= n && x + mid - 1 <= n; ++x) {
            while (top < sz(cc) && cc[top].x < x) {
                update(1, 1, m, cc[top].l, cc[top].r, cc[top].val);
                top++;
            }
            while (top < sz(cc) && cc[top].x == x && cc[top].add == 1) {
                update(1, 1, m, cc[top].l, cc[top].r, cc[top].val);
                top++;
            }

            ll val = get(1, 1, m, 1, m - mid + 1);

            if (val <= B) {
                flag = true;
                break;
            }

        }

        if (flag) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }


    }

    cout << ans << "\n";
}

signed main() {
#ifdef zxc
    debug = 1;
    freopen("../input.txt", "r", stdin);
    //freopen("../output.txt", "w", stdout);
#else
    //freopen("roboherd.in", "r", stdin);
    //freopen("roboherd.out", "w", stdout);

#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(20);

    int t = 1;
    while (t--)
        solve();
    if (debug)
        cerr << endl << "time : " << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 760 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2600 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 16960 KB Output is correct
2 Correct 218 ms 16860 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 16976 KB Output is correct
2 Correct 164 ms 16964 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1600 KB Output is correct
2 Correct 64 ms 1564 KB Output is correct
3 Correct 54 ms 1612 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 6148 KB Output is correct
2 Correct 459 ms 6360 KB Output is correct
3 Correct 378 ms 6096 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 35856 KB Output is correct
2 Correct 87 ms 2944 KB Output is correct
3 Correct 235 ms 35744 KB Output is correct
4 Correct 1516 ms 35936 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1459 ms 36144 KB Output is correct
2 Correct 2832 ms 36280 KB Output is correct
3 Correct 840 ms 36204 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1272 ms 36480 KB Output is correct
2 Correct 3129 ms 36564 KB Output is correct
3 Correct 2953 ms 36544 KB Output is correct
4 Correct 3273 ms 36644 KB Output is correct
5 Correct 3210 ms 36580 KB Output is correct
6 Correct 720 ms 36552 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5019 ms 39072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5047 ms 55240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5103 ms 60948 KB Time limit exceeded
2 Halted 0 ms 0 KB -