Submission #560364

#	Time	Username	Problem	Language	Result	Execution time	Memory
560364		SSRS	Pyramid Base (IOI08_pyramid_base)	C++14	70 / 100	5077 ms	111744 KiB

pyramid_base

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000;
struct segment_tree{
  int N;
  vector<long long> sum, left;
  segment_tree(int N2){
    N = 1;
    while (N < N2){
      N *= 2;
    }
    sum = vector<long long>(N * 2 - 1, INF);
    left = vector<long long>(N * 2 - 1, INF);
    for (int i = 0; i < N2; i++){
      sum[N - 1 + i] = 0;
      left[N - 1 + i] = 0;
    }
    for (int i = N - 2; i >= 0; i--){
      sum[i] = sum[i * 2 + 1] + sum[i * 2 + 2];
      left[i] = 0;
    }
  }
  void add(int i, long long x){
    i += N - 1;
    sum[i] += x;
    left[i] = sum[i];
    while (i > 0){
      i = (i - 1) / 2;
      sum[i] = sum[i * 2 + 1] + sum[i * 2 + 2];
      left[i] = min(left[i * 2 + 1], sum[i * 2 + 1] + min(left[i * 2 + 2], (long long) 0));
    }
  }
  long long get(){
    return left[0];
  }
};
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int M, N;
  cin >> M >> N;
  int B;
  cin >> B;
  int P;
  cin >> P;
  vector<int> X1(P), Y1(P), X2(P), Y2(P), C(P);
  for (int i = 0; i < P; i++){
    cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i] >> C[i];
    X1[i]--;
    Y1[i]--;
  }
  int tv = 0, fv = min(M, N) + 1;
  while (fv - tv > 1){
    int mid = (tv + fv) / 2;
    vector<vector<int>> add(N - mid + 2), sub(N - mid + 2);
    for (int i = 0; i < P; i++){
      add[max(Y1[i] - mid + 1, 0)].push_back(i);
      sub[min(Y2[i], N - mid + 1)].push_back(i);
    }
    segment_tree ST(M - mid + 1);
    bool ok = false;
    for (int i = 0; i < N - mid + 1; i++){
      for (int j : add[i]){
        ST.add(max(X1[j] - mid + 1, 0), C[j]);
        if (X2[j] < M - mid + 1){
          ST.add(X2[j], -C[j]);
        }
      }
      for (int j : sub[i]){
        ST.add(max(X1[j] - mid + 1, 0), -C[j]);
        if (X2[j] < M - mid + 1){
          ST.add(X2[j], C[j]);
        }
      }
      if (ST.get() <= B){
        ok = true;
      }
    }
    if (ok){
      tv = mid;
    } else {
      fv = mid;
    }
  }
  cout << tv << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10