oj.uz

Submission #132939

# Submission time Handle Problem Language Result Execution time Memory
132939 2019-07-20T02:19:18 Z letrongdat Pyramid Base (IOI08_pyramid_base) C++17
80 / 100
 5000 ms 108032 KB 
#include <bits/stdc++.h>
using namespace std;
#define FORN(i, a, b)               for(int i=a; i<=b; ++i)
#define FORD(i, a, b)               for(int i=a; i>=b; --i)
#define REPN(i, a, b)               for(int i=a; i <b; ++i)
#define REPD(i, a, b)               for(int i=(int)a-1; i>=b; --i)
const int maxR = 4*1e5 +10;
const int maxN = 1e6 +10;
const int INF = 1e9 +7;
int M, N, B, P;
typedef tuple<int, int, int> i3;
vector< i3 > open[maxN], close[maxN];
struct Rectangle {
    int x1, y1, x2, y2, cost;
    Rectangle(){};
    Rectangle(int x1, int y1, int x2, int y2): x1(x1), y1(y1), x2(x2), y2(y2) {};
    void expand(int d, int id = 0) {
        open[max(1, x1-d)].push_back({max(1, y1-d), y2, cost});
        close[x2].push_back({max(1, y1-d), y2, cost});
        open[x2+1].push_back({1, P+1, 0});
    }
    friend istream & operator >> (istream &is, Rectangle &T) {
        is >> T.x1 >> T.y1 >> T.x2 >> T.y2 >> T.cost;
        return is;
    }
} rec[maxR];
namespace subtask2 {
#define ii      pair<int, int>
    int a[maxN];
    int it[4*maxN], t[4*maxN];
    void lazy(int x, int l, int r) {
        it[x] += t[x];
        if (l != r) {
            t[2*x] += t[x];
            t[2*x+1] += t[x];
        }
        t[x] = 0;
    }
    void update(int x, int l, int r, int i, int j, int cost) {
        lazy(x, l, r);
        if (a[r] < i || j < a[l]) return;
        if (i <= a[l] && a[r] <= j) {
            t[x] = cost;
            lazy(x, l, r);
            return;
        }
        int m = l+r >> 1;
        update(2*x, l, m, i, j, cost);
        update(2*x+1, m+1, r, i, j, cost);
        it[x] = min(it[2*x], it[2*x+1]);
    }
    int query(int x, int l, int r, int i, int j) {
        lazy(x, l, r);
        if (a[r] < i || j < a[l]) return INF;
        if (i <= a[l] && a[r] <= j) return it[x];
        int m = l+r >> 1;
        return min(query(2*x, l, m, i, j), query(2*x+1, m+1, r, i, j));
    }
    bool ok(int d) {
        FORN(i, 1, P) rec[i].expand(d -1, 1);
        int result = INF;
        open[1].push_back({1, N-d+1, 0});
        FORN(i, 0, M) {
            if (open[i].size()) {
                for(auto ss: open[i]) {
                    int y1, y2, cost;
                    tie(y1, y2, cost) = ss;
                    update(1, 1, P+1, y1, y2, cost);
                }
                if (i <= M-d+1) result = min(result, query(1, 1, P+1, 1, N-d+1));
            }   
            if (close[i].size()) {       
                for(auto ss: close[i]) {
                    int y1, y2, cost;
                    tie(y1, y2, cost) = ss;
                    update(1, 1, P+1, y1, y2, -cost);
                }
            }   
        }
        FORN(i, 1, M) open[i].clear(), close[i].clear();
        return (result <= B);
    }
    void run() {
        FORN(i, 1, P) a[i] = rec[i].y2 + 1;
        a[P+1] = 1;
        sort(a+1, a+P+2);
        int low = 0, high = min(M, N), result = 0;
        while (low <= high) {
            int mid = low + high >> 1;
            if (ok(mid)) {
                result = mid;
                low = mid+1;
            } else high = mid-1;
        }
        cout << result << '\n';
    }
}
namespace subtask3 {
    int result = 0;
    int mx[4*maxN], le[4*maxN], ri[4*maxN], cnt[4*maxN];

    void lazy(int x, int l, int r) {
        int m = l+r >> 1;
        if (l<r) {
            mx[x] = max(max(mx[2*x], mx[2*x+1]), ri[2*x] + le[2*x+1]);
            le[x] = (le[2*x] >= m-l+1 ? le[2*x] + le[2*x+1] : le[2*x]);
            ri[x] = (ri[2*x+1] >= r-m ? ri[2*x+1] + ri[2*x] : ri[2*x+1]);
        } else mx[x] = le[x] = ri[x] = 1;
    }
    void update(int x, int l, int r, int i, int j, int cost) {
        if (j < l || r < i) return;
        if (i <= l && r <= j) {
            cnt[x] += cost;
            assert(cnt[x] >=0);
            if (cnt[x]) mx[x] = le[x] = ri[x] = 0;
                else lazy(x, l, r);
            return;
        }
        int m = l+r >> 1;
        update(2*x, l, m, i, j, cost);
        update(2*x+1, m+1, r, i, j, cost);
        if (cnt[x] == 0) lazy(x, l, r);
    }
    bool ok(int l, int r) {
        for(auto ss: open[r]) {
            int y1, y2, cost;
            tie(y1, y2, cost) = ss;
            update(1, 1, N, y1, y2, 1);
            close[rec[cost].x2].push_back({y1, y2, cost});
        }
        if (mx[1] >= r-l+1) return true;
        for(auto ss: open[r]) {
            int y1, y2, cost;
            tie(y1, y2, cost) = ss;
            update(1, 1, N, y1, y2, -1);
            close[rec[cost].x2].pop_back();
        }
        return false;
    }
    void build(int x, int l, int r) {
        mx[x] = le[x] = ri[x] = r-l+1;
        if (l == r) return;
        int m = l+r >> 1;
        build(2*x, l, m);
        build(2*x+1, m+1, r);
    }
    void run() {
        build(1, 1, N);
        FORN(i, 1, P) open[rec[i].x1].push_back({rec[i].y1, rec[i].y2, i});
        int ri = 0;
        FORN(i, 1, M) {
            ri = max(ri, i);
            while (ri <= M && ok(i, ri)) ri ++;
            result = max(result, ri-i);
            for(auto ss: close[i]) {
                int y1, y2, cost;
                tie(y1, y2, cost) = ss;
                update(1, 1, N, y1, y2, -1);
            }
        }
        cout << result << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin >> M >> N >> B >> P;
    FORN(i, 1, P) cin >> rec[i];
    if (P <= 3e4) subtask2::run();
        else subtask3::run();
    return 0;
}

Compilation message

pyramid_base.cpp: In function 'void subtask2::update(int, int, int, int, int, int)':
pyramid_base.cpp:47:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l+r >> 1;
                 ~^~
pyramid_base.cpp: In function 'int subtask2::query(int, int, int, int, int)':
pyramid_base.cpp:56:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l+r >> 1;
                 ~^~
pyramid_base.cpp: In function 'void subtask2::run()':
pyramid_base.cpp:89:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid = low + high >> 1;
                       ~~~~^~~~~~
pyramid_base.cpp: In function 'void subtask3::lazy(int, int, int)':
pyramid_base.cpp:103:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l+r >> 1;
                 ~^~
pyramid_base.cpp: In function 'void subtask3::update(int, int, int, int, int, int)':
pyramid_base.cpp:119:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l+r >> 1;
                 ~^~
pyramid_base.cpp: In function 'void subtask3::build(int, int, int)':
pyramid_base.cpp:143:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l+r >> 1;
                 ~^~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 47744 KB Output is correct
2 Correct 346 ms 48060 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 48124 KB Output is correct
2 Correct 303 ms 47744 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 48124 KB Output is correct
2 Correct 140 ms 48300 KB Output is correct
3 Correct 136 ms 48444 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 50944 KB Output is correct
2 Correct 596 ms 51636 KB Output is correct
3 Correct 489 ms 52396 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1088 ms 54192 KB Output is correct
2 Correct 433 ms 53632 KB Output is correct
3 Correct 253 ms 50224 KB Output is correct
4 Correct 1276 ms 57848 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1370 ms 57092 KB Output is correct
2 Correct 1376 ms 61576 KB Output is correct
3 Correct 1061 ms 52148 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1388 ms 55476 KB Output is correct
2 Correct 1725 ms 62844 KB Output is correct
3 Correct 1700 ms 62704 KB Output is correct
4 Correct 1758 ms 62836 KB Output is correct
5 Correct 1730 ms 63128 KB Output is correct
6 Correct 1115 ms 51612 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1400 ms 95900 KB Output is correct
2 Correct 509 ms 61652 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1513 ms 102500 KB Output is correct
2 Execution timed out 5016 ms 94436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1744 ms 107572 KB Output is correct
2 Correct 2005 ms 108032 KB Output is correct
3 Incorrect 2028 ms 107948 KB Output isn't correct
4 Halted 0 ms 0 KB -