oj.uz

Submission #401904

# Submission time Handle Problem Language Result Execution time Memory
401904 2021-05-11T01:03:11 Z ja_kingy Pyramid Base (IOI08_pyramid_base) C++14
0 / 100
 5000 ms 42620 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;
const int mxP = 4e5;
int m,n,b,p,x1[mxP],y1[mxP],x2[mxP],y2[mxP],c[mxP];
vector<pii> lft, rht;

struct range_add {
    int st[1<<21], lz[1<<21];
    void push(int t) {
        st[t*2] += lz[t];
        st[t*2+1] += lz[t];
        lz[t*2] += lz[t];
        lz[t*2+1] += lz[t];
        lz[t] = 0;
    }
    void upd(int ul, int ur, int v, int t, int l, int r) {
        if (ur <= l || r <= ul) return;
        if (ul <= l && r <= ur) {
            st[t] += v;
            lz[t] += v;
            return;
        }
        int m = l+r>>1;
        push(t);
        upd(ul, ur, v, t*2, l, m);  
        upd(ul, ur, v, t*2+1, m, r);
        st[t] = min(st[t*2], st[t*2+1]);  
    }
};

bool can_do(int sz) {
    range_add st;
    int l = 0;
    for (auto [x, s]: rht) {
        if (~s) st.upd(y1[s]-sz+1, y2[s]+1, -c[s], 1, 1, n-sz+1);
        while (l < lft.size() && lft[l].first - x <= sz) {
            st.upd(y1[lft[l].second]-sz+1, y2[lft[l].second]+1, c[lft[l].second], 1, 1, n-sz+1);
            l++;
        }
        if (l == lft.size()) return 0;
        if (st.st[1] <= b) return 1;
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n >> b >> p;
    lft.push_back({m+1, -1});
    rht.push_back({0, -1});
    for (int i = 0; i < p; ++i) {
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i] >> c[i];
        lft.push_back({x1[i], i});
        rht.push_back({x2[i], i});
    }
    sort(lft.begin(), lft.end());
    sort(rht.begin(), rht.end());
    int lo = 1, hi = min(m,n)+1, mid;
    while (lo != hi) {
        mid = lo+hi>>1;
        if (can_do(mid)) lo = mid+1;
        else hi = mid;
    }
    cout << lo-1;
}

Compilation message

pyramid_base.cpp: In member function 'void range_add::upd(int, int, int, int, int, int)':
pyramid_base.cpp:27:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         int m = l+r>>1;
      |                 ~^~
pyramid_base.cpp: In function 'bool can_do(int)':
pyramid_base.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for (auto [x, s]: rht) {
      |               ^
pyramid_base.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         while (l < lft.size() && lft[l].first - x <= sz) {
      |                ~~^~~~~~~~~~~~
pyramid_base.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if (l == lft.size()) return 0;
      |             ~~^~~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         mid = lo+hi>>1;
      |               ~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 16716 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 16716 KB Output isn't correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 16716 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 16816 KB Output isn't correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 16828 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 16716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 16808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 17116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 17740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 18260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 653 ms 18576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 395 ms 18896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5033 ms 29772 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 5075 ms 36188 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 5084 ms 42620 KB Time limit exceeded
2 Halted 0 ms 0 KB -