oj.uz

답안 #446612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446612 2021-07-22T18:43:32 Z JerryLiu06 Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
 1750 ms 142328 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert 
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)
 
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
template<class T> void remDup(vector<T>& v) { sor(v); v.erase(unique(all(v)), v.end()); }
 
const int MOD = 1e9 + 7;
const int MX = 1e6 + 10;
const ll INF = 1e18;
 
int M, N, B, P;
 
struct Subtask2 {
    vector<array<int, 3>> ST[MX], EN[MX]; int tree[4 * MX], lazy[4 * MX];
 
    void pushdown(int x, int l, int r) {
        if (lazy[x] == 0) return ; tree[x] += lazy[x];
 
        if (l < r) { F0R(i, 2) lazy[2 * x + i] += lazy[x]; } lazy[x] = 0;
    }
    void update(int x, int l, int r, int tl, int tr, int val) { int mid = (l + r) / 2;
        pushdown(x, l, r); if (l > tr || r < tl) return ; if (tl <= l && r <= tr) { lazy[x] = val; pushdown(x, l, r); return ; }
 
        update(2 * x, l, mid, tl, tr, val); update(2 * x + 1, mid + 1, r, tl, tr, val); tree[x] = min(tree[2 * x], tree[2 * x + 1]);
    }
 
    void init() {
        F0R(i, P) {
            int X1, Y1, X2, Y2, C; cin >> X1 >> Y1 >> X2 >> Y2 >> C;
 
            ST[X1].pb({Y1, Y2, C}); EN[X2 + 1].pb({Y1, Y2, -C});
        }
    }
    int solve() {
        int low = 0; int high = min(M, N); int res = 0;
 
        while (low <= high) { int mid = (low + high) / 2; 
            F0R(i, 4 * N) tree[i] = 0, lazy[i] = 0; update(1, 1, N, N - mid + 2, N, MOD);
 
            FOR(i, 1, mid) EACH(C, ST[i]) update(1, 1, N, max(1, C[0] - mid + 1), C[1], C[2]);
 
            bool valid = false; FOR(i, 1, M - mid + 2) {
                EACH(C, ST[i + mid - 1]) update(1, 1, N, max(1, C[0] - mid + 1), C[1], C[2]);
                
                EACH(C, EN[i]) update(1, 1, N, max(1, C[0] - mid + 1), C[1], C[2]);
                
                valid = tree[1] <= B; if (valid) break;
            }
            if (valid) low = mid + 1, res = mid; else high = mid - 1;
        }
        return res;
    }
};
 
struct Subtask3 {
    vector<array<int, 2>> ST[MX], EN[MX];
 
    struct Node { int L, R, ans; } tree[4 * MX]; int lazy[4 * MX];
 
    void comb(int x, int l, int r) { int mid = (l + r) / 2;
        int LL = tree[2 * x].L, LR = tree[2 * x].R, LA = tree[2 * x].ans;
        int RL = tree[2 * x + 1].L, RR = tree[2 * x + 1].R, RA = tree[2 * x + 1].ans;
 
        if (lazy[2 * x]) LL = LR = LA = 0; if (lazy[2 * x + 1]) RL = RR = RA = 0;
 
        tree[x].ans = max({LA, RA, LR + RL}); tree[x].L = LL == mid - l + 1 ? (LL + RL) : LL; tree[x].R = RR == r - mid ? (RR + LR) : RR;
    }
    void build(int x, int l, int r) { int mid = (l + r) / 2;
        if (l == r) { tree[x].L = tree[x].R = tree[x].ans = 1; return ; }
 
        build(2 * x, l, mid); build(2 * x + 1, mid + 1, r); comb(x, l, r);
    }
    void update(int x, int l, int r, int tl, int tr, int val) { int mid = (l + r) / 2;
        if (l > tr || r < tl) return ; if (tl <= l && r <= tr) { lazy[x] += val; return ; }
 
        update(2 * x, l, mid, tl, tr, val); update(2 * x + 1, mid + 1, r, tl, tr, val); comb(x, l, r);
    }
 
    void init() {
        F0R(i, P) {
            int X1, Y1, X2, Y2, C; cin >> X1 >> Y1 >> X2 >> Y2 >> C;
 
            ST[X1].pb({Y1, Y2}); EN[X2 + 1].pb({Y1, Y2});
        }
    }
    int solve() {
        int ans = 0; int R = 1; build(1, 1, N);
 
        FOR(L, 1, M + 1) {
            EACH(C, EN[L]) update(1, 1, N, C[0], C[1], -1);
 
            while (R <= M + 1 && (lazy[1] ? 0 : tree[1].ans) >= R - L) {
                
                ckmax(ans, R - L);
                
                EACH(C, ST[R]) update(1, 1, N, C[0], C[1], 1); R++; 
            }
        }
        return ans;
    }
};
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    cin >> M >> N >> B >> P; if (B) { Subtask2 S; S.init(); cout << S.solve(); } else { Subtask3 S; S.init(); cout << S.solve(); }
}

Compilation message

pyramid_base.cpp: In member function 'void Subtask2::pushdown(int, int, int)':
pyramid_base.cpp:65:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   65 |         if (lazy[x] == 0) return ; tree[x] += lazy[x];
      |         ^~
pyramid_base.cpp:65:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   65 |         if (lazy[x] == 0) return ; tree[x] += lazy[x];
      |                                    ^~~~
pyramid_base.cpp: In member function 'int Subtask2::solve()':
pyramid_base.cpp:41:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   41 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                      ^~~
pyramid_base.cpp:42:19: note: in expansion of macro 'FOR'
   42 | #define F0R(i, a) FOR(i, 0, a)
      |                   ^~~
pyramid_base.cpp:86:13: note: in expansion of macro 'F0R'
   86 |             F0R(i, 4 * N) tree[i] = 0, lazy[i] = 0; update(1, 1, N, N - mid + 2, N, MOD);
      |             ^~~
pyramid_base.cpp:86:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   86 |             F0R(i, 4 * N) tree[i] = 0, lazy[i] = 0; update(1, 1, N, N - mid + 2, N, MOD);
      |                                                     ^~~~~~
pyramid_base.cpp: In member function 'void Subtask3::comb(int, int, int)':
pyramid_base.cpp:112:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  112 |         if (lazy[2 * x]) LL = LR = LA = 0; if (lazy[2 * x + 1]) RL = RR = RA = 0;
      |         ^~
pyramid_base.cpp:112:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  112 |         if (lazy[2 * x]) LL = LR = LA = 0; if (lazy[2 * x + 1]) RL = RR = RA = 0;
      |                                            ^~
pyramid_base.cpp: In member function 'void Subtask3::update(int, int, int, int, int, int)':
pyramid_base.cpp:122:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  122 |         if (l > tr || r < tl) return ; if (tl <= l && r <= tr) { lazy[x] += val; return ; }
      |         ^~
pyramid_base.cpp:122:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  122 |         if (l > tr || r < tl) return ; if (tl <= l && r <= tr) { lazy[x] += val; return ; }
      |                                        ^~
pyramid_base.cpp: In member function 'int Subtask3::solve()':
pyramid_base.cpp:45:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   45 | #define EACH(a, x) for (auto& a : x)
      |                    ^~~
pyramid_base.cpp:144:17: note: in expansion of macro 'EACH'
  144 |                 EACH(C, ST[R]) update(1, 1, N, C[0], C[1], 1); R++;
      |                 ^~~~
pyramid_base.cpp:144:64: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  144 |                 EACH(C, ST[R]) update(1, 1, N, C[0], C[1], 1); R++;
      |                                                                ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 109764 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 109992 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 109824 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 109892 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 109888 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 109904 KB Output is correct
2 Correct 82 ms 109908 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 109884 KB Output is correct
2 Correct 79 ms 109948 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 110148 KB Output is correct
2 Correct 115 ms 110228 KB Output is correct
3 Correct 103 ms 110136 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 284 ms 111128 KB Output is correct
2 Correct 424 ms 111156 KB Output is correct
3 Correct 368 ms 111056 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 656 ms 111696 KB Output is correct
2 Correct 88 ms 111548 KB Output is correct
3 Correct 262 ms 111116 KB Output is correct
4 Correct 777 ms 111752 KB Output is correct

Subtask #11
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 908 ms 112148 KB Output is correct
2 Correct 1338 ms 111980 KB Output is correct
3 Correct 669 ms 112324 KB Output is correct

Subtask #12
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 995 ms 112600 KB Output is correct
2 Correct 1539 ms 112608 KB Output is correct
3 Correct 1639 ms 112452 KB Output is correct
4 Correct 1750 ms 112456 KB Output is correct
5 Correct 1657 ms 112476 KB Output is correct
6 Correct 746 ms 112672 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 700 ms 127044 KB Output is correct
2 Correct 386 ms 121284 KB Output is correct

Subtask #14
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 980 ms 134996 KB Output is correct
2 Correct 917 ms 131008 KB Output is correct
3 Correct 555 ms 124224 KB Output is correct

Subtask #15
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1166 ms 142328 KB Output is correct
2 Correct 1524 ms 139780 KB Output is correct
3 Correct 1378 ms 139464 KB Output is correct
4 Correct 1192 ms 137560 KB Output is correct
5 Correct 807 ms 132552 KB Output is correct