oj.uz

Submission #503408

# Submission time Handle Problem Language Result Execution time Memory
503408 2022-01-07T20:41:02 Z 600Mihnea Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
 2608 ms 149248 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Rect {
  int x1;
  int y1;
  int x2;
  int y2;
  int cost;
};

const int N = (int) 4e5 + 7;
const int L = (int) 1e6 + 7;
const int INF = (int) 1e9 + 7;
int dimx;
int dimy;
int budget;
int n;
int initN;
Rect rects[N], initRects[N];

struct Node {
  ll mn;
  int len;
  int sol;
  int pref;
  int suf;
};

Node tree[4 * L];
ll lazy[4 * L];

Node operator + (Node a, Node b) {
  int mn = min(a.mn, b.mn);
  int len = a.len + b.len;
  int sol;
  int pref;
  int suf;
  if (a.mn == b.mn) {
    sol = max(a.suf + b.pref, max(a.sol, b.sol));
    pref = a.pref + b.pref * (a.pref == a.len);
    suf = b.suf + a.suf * (b.suf == b.len);
  } else {
    if (a.mn < b.mn) {
      sol = a.sol;
      pref = a.pref;
      suf = 0;
    } else {
      sol = b.sol;
      pref = 0;
      suf = b.suf;
    }
  }
  return {mn, len, sol, pref, suf};
}

void build(int v, int tl, int tr) {
  lazy[v] = 0;
  if (tl == tr) {
    tree[v].mn = 0;
    tree[v].len = 1;
    tree[v].sol = 1;
    tree[v].pref = 1;
    tree[v].suf = 1;
    return;
  }
  int tm = (tl + tr) / 2;
  build(2 * v, tl, tm);
  build(2 * v + 1, tm + 1, tr);
  tree[v] = tree[2 * v] + tree[2 * v + 1];
}

void push(int v, int tl, int tr) {
  if (lazy[v]) {
    tree[v].mn += lazy[v];
    if (tl < tr) {
      lazy[2 * v] += lazy[v];
      lazy[2 * v + 1] += lazy[v];
    }
    lazy[v] = 0;
  }
}

void add(int v, int tl, int tr, int l, int r, int x) {
  push(v, tl, tr);
  if (tr < l || r < tl) {
    return;
  }
  if (l <= tl && tr <= r) {
    lazy[v] += x;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  add(2 * v, tl, tm, l, r, x);
  add(2 * v + 1, tm + 1, tr, l, r, x);
  tree[v] = tree[2 * v] + tree[2 * v + 1];
}

void build() {
  build(1, 1, dimy);
}

void add(int l, int r, int x) {
  add(1, 1, dimy, l, r, x);
}

int get() {
  /// cout << tree[1].mn << " " << tree[1].len << " ---> " << tree[1].sol << "\n";
  if (tree[1].mn == 0) {
    return tree[1].sol;
  } else {
    return 0;
  }
}

vector<int> out[L];
vector<int> in[L];

bool isok(int len) {
  rects[n + 1].x1 = dimx - len + 2;
  rects[n + 1].y1 = 1;
  rects[n + 1].x2 = dimx;
  rects[n + 1].y2 = dimy;
  rects[n + 1].cost = INF;

  rects[n + 2].x1 = 1;
  rects[n + 2].y1 = dimy - len + 2;
  rects[n + 2].x2 = dimx;
  rects[n + 2].y2 = dimy;
  rects[n + 2].cost = INF;

  for (int i = 1; i <= n; i++) {
    rects[i] = initRects[i];
    rects[i].x1 = max(1, rects[i].x1 - len + 1);
    rects[i].y1 = max(1, rects[i].y1 - len + 1);
  }

  for (int i = 0; i <= dimx + 1; i++) {
    in[i].clear();
    out[i].clear();
  }
  for (int i = 1; i <= n + 2; i++) {
    in[rects[i].x1].push_back(i);
    out[rects[i].x2 + 1].push_back(i);
  }

  build();

  for (int x = 1; x <= dimx; x++) {
    for (auto &i : in[x]) add(rects[i].y1, rects[i].y2, rects[i].cost);
    for (auto &i : out[x]) add(rects[i].y1, rects[i].y2, -rects[i].cost);
    if (tree[1].mn <= budget) {
      return 1;
    }
  }
  return 0;

}


signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

 /// freopen ("input", "r", stdin);

  cin >> dimx >> dimy >> budget >> n;
  initN = n;
  for (int i = 1; i <= n; i++) {
    cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2 >> rects[i].cost;
    in[rects[i].x1].push_back(i);
    out[rects[i].x2].push_back(i);
    initRects[i] = rects[i];
  }

  build();

  if (budget) {
    ///assert(0);
    ///cout << "I will think later about how to solve this subtask\n";
    int low = 1, high = min(dimx, dimy), solution = 0;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (isok(mid)) {
        solution = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    cout << solution << "\n";
    return 0;
  }

  int missed = 0;


  int x2 = 0, sol = 0;
  for (int x1 = 1; x1 <= dimx; x1++) {
    if (x2 >= x1 - 1) {
      for (auto &i : out[x1 - 1]) {
        add(rects[i].y1, rects[i].y2, -1);
      }
    }
    x2 = max(x2, x1 - 1);
    while (x2 <= dimx && x2 - x1 + 1 <= get()) {
      x2++;
      for (auto &i : in[x2]) {
        add(rects[i].y1, rects[i].y2, +1);
      }
      if (x2 - x1 + 1 > get()) {
        break;
      }
    }
    sol = max(sol, x2 - x1);
  }
  cout << sol << "\n";



  return 0;
}

Compilation message

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:198:7: warning: unused variable 'missed' [-Wunused-variable]
  198 |   int missed = 0;
      |       ^~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 113040 KB Output is correct
2 Correct 84 ms 113052 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 112944 KB Output is correct
2 Correct 87 ms 113012 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 48848 KB Output is correct
2 Correct 116 ms 48956 KB Output is correct
3 Correct 96 ms 49036 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 59060 KB Output is correct
2 Correct 636 ms 59424 KB Output is correct
3 Correct 553 ms 59864 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1283 ms 119684 KB Output is correct
2 Correct 118 ms 53828 KB Output is correct
3 Correct 419 ms 114756 KB Output is correct
4 Correct 1363 ms 123808 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1663 ms 122872 KB Output is correct
2 Correct 2033 ms 125028 KB Output is correct
3 Correct 1301 ms 117732 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1831 ms 121316 KB Output is correct
2 Correct 2489 ms 127708 KB Output is correct
3 Correct 2453 ms 127964 KB Output is correct
4 Correct 2608 ms 128556 KB Output is correct
5 Correct 2532 ms 128708 KB Output is correct
6 Correct 1369 ms 118376 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 132144 KB Output is correct
2 Correct 364 ms 69552 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 140936 KB Output is correct
2 Correct 998 ms 137016 KB Output is correct
3 Correct 585 ms 128924 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1334 ms 149248 KB Output is correct
2 Correct 1421 ms 146696 KB Output is correct
3 Correct 1424 ms 146692 KB Output is correct
4 Correct 1305 ms 144340 KB Output is correct
5 Correct 871 ms 138820 KB Output is correct