oj.uz

Submission #126012

# Submission time Handle Problem Language Result Execution time Memory
126012 2019-07-06T17:58:32 Z the_art_of_war Pyramid Base (IOI08_pyramid_base) C++14
70 / 100
 5000 ms 85868 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 void push(int v) {
    if (add[v]) {
        add[v << 1] += add[v];
        add[v << 1 | 1] += add[v];
        add[v] = 0;
    }
}

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;
        push(v);
        ll val1 = get(left, l, r);
        ll val2 = get(right, l, r);
        upd(v);
        return min(val1, val2);
    }
}

int c[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];
    }

    int l = 1, r = min(n, m);
    int ans = 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 = 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 376 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1016 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 4688 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 33364 KB Output is correct
2 Correct 2962 ms 33372 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2710 ms 33400 KB Output is correct
2 Correct 956 ms 33528 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1560 KB Output is correct
2 Correct 68 ms 1596 KB Output is correct
3 Correct 59 ms 1568 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 6204 KB Output is correct
2 Correct 513 ms 6264 KB Output is correct
3 Correct 461 ms 6192 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1010 ms 35948 KB Output is correct
2 Correct 99 ms 2916 KB Output is correct
3 Correct 235 ms 35748 KB Output is correct
4 Correct 1925 ms 35972 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1855 ms 36252 KB Output is correct
2 Correct 3925 ms 36160 KB Output is correct
3 Correct 923 ms 36136 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1505 ms 36492 KB Output is correct
2 Correct 4188 ms 36632 KB Output is correct
3 Correct 3973 ms 36620 KB Output is correct
4 Correct 4330 ms 36724 KB Output is correct
5 Correct 4314 ms 36600 KB Output is correct
6 Correct 763 ms 36732 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5103 ms 58244 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 5007 ms 77284 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 5054 ms 85868 KB Time limit exceeded
2 Halted 0 ms 0 KB -