oj.uz

Submission #965592

# Submission time Handle Problem Language Result Execution time Memory
965592 2024-04-19T01:57:32 Z idiotcomputer Pyramid Base (IOI08_pyramid_base) C++11
90 / 100
 5000 ms 49764 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<ll,ll>
#define f first
#define s second 
#define ll long long int 

const int mxP = 4e5;
const int mxN = 1e6;
int n,m;

ll segtree[4*mxN+1];
ll laz[4*mxN+1];
int curr;

void build(int l = 0, int r = n-1, int idx = 0){
    if (r+1<curr){
        segtree[idx] = 2e9+1;
        laz[idx] = 0;
        return;
    }
    segtree[idx] = 0;
    laz[idx] = 0;
    if (l == r) return;
    int m = (l+r)/2;
    build(l,m,2*idx+1);
    build(m+1,r,2*idx+2);
}

void upd(int tl, int tr, ll v, int l = 0, int r = n-1, int idx = 0){
    if (l > tr || r < tl || r+1<curr) return;
    if (l >= tl && r <= tr){
        laz[idx] += v;
        return;
    }
    int m = (l+r)/2;
    upd(tl,tr,v,l,m,2*idx+1);
    upd(tl,tr,v,m+1,r,2*idx+2);
    segtree[idx] = min(segtree[2*idx+1]+laz[2*idx+1],segtree[2*idx+2]+laz[2*idx+2]);
}

void build1(int l = 0, int r = n-1, int idx = 0){
    if (r+1<curr){
        segtree[idx] = m+1;
        laz[idx] = m+1;
        return;
    }
    segtree[idx] = 0;
    laz[idx] = 0;
    if (l == r) return;
    int m = (l+r)/2;
    build1(l,m,2*idx+1);
    build1(m+1,r,2*idx+2);
}
 
void upd1(int tl, int tr, ll v, int l = 0, int r = n-1, int idx = 0){
    if (l > tr || r < tl || r+1<curr) return;
    if (l >= tl && r <= tr){
        laz[idx] = max(laz[idx],v);
        return;
    }
    laz[2*idx+1] = max(laz[idx],laz[2*idx+1]);
    laz[2*idx+2] = max(laz[idx],laz[2*idx+2]);
    laz[idx] = 0;
    int m = (l+r)/2;
    upd1(tl,tr,v,l,m,2*idx+1);
    upd1(tl,tr,v,m+1,r,2*idx+2);
    segtree[idx] = min(max(segtree[2*idx+1],laz[2*idx+1]),max(segtree[2*idx+2],laz[2*idx+2]));
}

void solve(int b, int p){
    int r[p];
    pii y[p];
    vector<pii> vals(p);
    int x1,y1,x2,y2,c1;
    for (int i =0; i < p; i++){
        cin >> x1 >> y1 >> x2 >> y2 >> c1;
        x1 -= 1;
        y1 -= 1;
        x2 -= 1;
        y2 -= 1;
        r[i] = x2;
        y[i] = {y1,y2};
        vals[i] = {x1,i};
    }
    sort(vals.begin(),vals.end());
    
    int start = 0;
    int end = min(n,m)+1;
    bool w;
    int best;
    while (end - start > 1){
        curr = (start+end)/2;
        build1();
        w = false;
        for (int i = 0; i < p; i++){
            best = max(laz[0],segtree[0]);
            if (vals[i].f-best >= curr){
                w = true;
                break;
            }
            upd1(y[vals[i].s].f,min((ll) n-1,y[vals[i].s].s+curr-1),r[vals[i].s]+1);
        }
        best = max(laz[0],segtree[0]);
        if (m-best >= curr) w = true;
        if (w) start = curr;
        else end = curr;
    }
    cout << start << "\n";
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll b;
    int p;
    cin >> m >> n >> b >> p;
    if (b == 0){
        solve(b,p);
        return 0;
    }
    
    pii x[p];
    pii y[p];
    ll c[p];
    ll x1,y1,x2,y2,c1;
    for (int i =0; i < p; i++){
        cin >> x1 >> y1 >> x2 >> y2 >> c1;
        x1 -= 1;
        y1 -= 1;
        x2 -= 1;
        y2 -= 1;
        x[i] = {x1,x2};
        y[i] = {y1,y2};
        c[i] = c1;
    }

    int start = 0;
    int end = min(n,m)+1;
    bool w;
    ll best;
    bool vis[p];
    int last;
    while (end - start > 1){
        curr = (start+end)/2;
        build();
        memset(vis,0,sizeof(vis));
        priority_queue<pii, vector<pii>, greater<pii>> queue;
        for (int i = 0; i < p; i++){
            queue.push({x[i].f,i});
            queue.push({x[i].s+curr,i});
        }
        w = false;
        last = -1;
        while (queue.size() > 0){
            pii cur = queue.top();
            queue.pop();
            if (cur.f >= m) break;
            
            best = laz[0]+segtree[0];
            if (last != cur.f && best <= b && cur.f >= curr){
                w = true;
                break;
            }
            last = cur.f;
            ll val = c[cur.s];
            if (vis[cur.s]) val *= -1;
            else vis[cur.s] = 1;
            upd(y[cur.s].f,min((ll) n-1,y[cur.s].s+curr-1),val);
        }
        best = laz[0]+segtree[0];
        if (best <= b) w = true;
        if (w) start = curr;
        else end = curr;
    }
    cout << start << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6768 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31324 KB Output is correct
2 Correct 103 ms 35528 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 35532 KB Output is correct
2 Correct 33 ms 31324 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5272 KB Output is correct
2 Correct 43 ms 5352 KB Output is correct
3 Correct 35 ms 5352 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 8276 KB Output is correct
2 Correct 239 ms 8368 KB Output is correct
3 Correct 190 ms 8372 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 33760 KB Output is correct
2 Correct 25 ms 4992 KB Output is correct
3 Correct 201 ms 37952 KB Output is correct
4 Correct 354 ms 37944 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 38712 KB Output is correct
2 Correct 692 ms 38308 KB Output is correct
3 Correct 160 ms 34352 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 34476 KB Output is correct
2 Correct 870 ms 38888 KB Output is correct
3 Correct 815 ms 38888 KB Output is correct
4 Correct 961 ms 38892 KB Output is correct
5 Correct 895 ms 38752 KB Output is correct
6 Correct 145 ms 34484 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2379 ms 42552 KB Output is correct
2 Correct 182 ms 13640 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3550 ms 46288 KB Output is correct
2 Correct 3482 ms 45904 KB Output is correct
3 Correct 2416 ms 45908 KB Output is correct

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4101 ms 49576 KB Output is correct
2 Execution timed out 5042 ms 49764 KB Time limit exceeded
3 Halted 0 ms 0 KB -