oj.uz

Submission #131793

# Submission time Handle Problem Language Result Execution time Memory
131793 2019-07-17T16:06:49 Z the_art_of_war Pyramid Base (IOI08_pyramid_base) C++14
100 / 100
 3397 ms 155744 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 = 2e6 + 100;
const int LOG = 25;
const int mod = 1e9 + 7;
const int MX = 2e6 + 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];



struct vertex {
    int pref, suf, val;
    int spec;
};


vertex t2[4 * MX];

void combine(int v, int tl, int tr, vertex &l, vertex &r) {
    if (t2[v].spec) {
        t2[v].pref = 0;
        t2[v].suf = 0;
        t2[v].val = 0;
    } else {
        if (tl < tr) {
            t2[v].pref = l.pref;
            t2[v].suf = r.suf;
            t2[v].val = max(l.val, max(r.val, l.suf + r.pref));
            int tm = (tl + tr) >> 1;
            if (l.val == tm - tl + 1) {
                assert(l.val == l.pref);
                t2[v].pref = l.pref + r.pref;
            }
            if (r.val == tr - tm) {
                assert(r.val == r.pref);
                t2[v].suf = r.suf + l.suf;
            }
        } else {
            t2[v].pref = t2[v].suf = t2[v].val = 1;
        }
    }
}


void build2(int v, int tl, int tr) {
    if (tl == tr) {
        t2[v].pref = t2[v].suf = t2[v].val = 1;
        t2[v].spec = 0;
    } else {
        int tm = (tl + tr) >> 1;
        build2(left);
        build2(right);
        combine(v, tl, tr, 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) {
        t2[v].spec += x;
        combine(v, tl, tr, t2[v << 1], t2[v << 1 | 1]);
        return;
    } else {
        int tm = (tl + tr) >> 1;
        update2(left, l, r, x);
        update2(right, l, r, x);
        combine(v, tl, tr, t2[v << 1], t2[v << 1 | 1]);
    }
}

vector<int> add_rec[MAXN];
vector<int> rem_rec[MAXN];


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];

        add_rec[x1[i]].pb(i);
        rem_rec[x2[i] + 1].pb(i);
    }

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

    if(B == 0) {
        assert(B == 0);
        build2(1, 1, m);
        dout << t2[1].val << endl;
        int r = 1;
        for (int v:add_rec[1]) {
            update2(1, 1, m, y1[v], y2[v], 1);
        }
        for (int i = 1; i <= n; ++i) {
            dout << i << " - " << r << endl;
            for (int v:rem_rec[i]) {
                update2(1, 1, m, y1[v], y2[v], -1);
                dout <<"update "<<y1[v]<<" "<<y2[v]<<" "<<-1<<endl;
            }
            while (r < i) {
                r++;
                for (int v:add_rec[r]) {
                    update2(1, 1, m, y1[v], y2[v], 1);
                    dout <<"update "<<y1[v]<<" "<<y2[v]<<" "<<1<<endl;
                }
            }

            while (r <= n && t2[1].val >= r - i + 1) {
                dout << i << " --- " << r << " " << t2[1].val << endl;
                ans = max(ans, r - i + 1);
                r++;
                for (int v:add_rec[r]) {
                    update2(1, 1, m, y1[v], y2[v], 1);
                    dout <<"update "<<y1[v]<<" "<<y2[v]<<" "<<1<<endl;
                }
            }
            dout << "last " << i << " - " << r << " :: " << ans << endl;
        }
        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 93 ms 94328 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 94300 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 94328 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 94840 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 98600 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 127224 KB Output is correct
2 Correct 156 ms 127308 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 127200 KB Output is correct
2 Correct 150 ms 127388 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 95764 KB Output is correct
2 Correct 181 ms 95716 KB Output is correct
3 Correct 149 ms 95724 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 100896 KB Output is correct
2 Correct 552 ms 101020 KB Output is correct
3 Correct 524 ms 100728 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 964 ms 131036 KB Output is correct
2 Correct 190 ms 98044 KB Output is correct
3 Correct 325 ms 129920 KB Output is correct
4 Correct 1673 ms 131136 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1557 ms 131656 KB Output is correct
2 Correct 2914 ms 131416 KB Output is correct
3 Correct 938 ms 131644 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1370 ms 132224 KB Output is correct
2 Correct 3223 ms 132324 KB Output is correct
3 Correct 3105 ms 132100 KB Output is correct
4 Correct 3397 ms 132284 KB Output is correct
5 Correct 3314 ms 132336 KB Output is correct
6 Correct 829 ms 132348 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 783 ms 142516 KB Output is correct
2 Correct 454 ms 108500 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1037 ms 149348 KB Output is correct
2 Correct 947 ms 145624 KB Output is correct
3 Correct 613 ms 137300 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1235 ms 155744 KB Output is correct
2 Correct 1403 ms 153336 KB Output is correct
3 Correct 1351 ms 153200 KB Output is correct
4 Correct 1241 ms 150888 KB Output is correct
5 Correct 956 ms 145224 KB Output is correct