Submission #807672

#	Time	Username	Problem	Language	Result	Execution time	Memory
807672		dong_liu	Food Court (JOI21_foodcourt)	C++17	100 / 100	340 ms	41692 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int N = 250000, N_ = 1 << 18, INF = 0x3f3f3f3f;

int n_;

array<LL, 2> st1[N_ * 2];

array<LL, 2> join(array<LL, 2> a, array<LL, 2> b) {
  return {a[0] + b[0], max(a[1] + b[0], b[1])};
}

void update1(int i, int x) {
  i |= n_;
  st1[i][0] = x;
  st1[i][1] = max(0, x);
  while (i >>= 1) st1[i] = join(st1[i << 1 | 0], st1[i << 1 | 1]);
}

LL query1(int l, int r) {
  vector<int> ll, rr;
  array<LL, 2> v = {0, 0};

  for (l |= n_, r |= n_; l <= r; l >>= 1, r >>= 1) {
    if ((l & 1) == 1) ll.push_back(l++);
    if ((r & 1) == 0) rr.push_back(r--);
  } 
  for (int i : ll) v = join(v, st1[i]);
  reverse(rr.begin(), rr.end());
  for (int i : rr) v = join(v, st1[i]);
  return v[1];
}

LL st2[N_ * 2];

void update2(int i, int x) {
  st2[i |= n_] = x;
  while (i >>= 1) st2[i] = st2[i << 1 | 0] + st2[i << 1 | 1];
}

LL query2(int l, int r) {
  LL sum = 0;

  for (l |= n_, r |= n_; l <= r; l >>= 1, r >>= 1) {
    if ((l & 1) == 1) sum += st2[l++];
    if ((r & 1) == 0) sum += st2[r--];
  }
  return sum;
}

int query3(LL x) {
  int i = 1;

  while (i < n_) {
    if (x <= st2[i << 1 | 0])
      i = i << 1 | 0;
    else {
      x -= st2[i << 1 | 0];
      i = i << 1 | 1;
    }
  }
  return i ^ n_;
}

vector<pair<int, int>> uu[N + 1];
vector<pair<int, LL>> qq[N];

void run() {
  static int cc[N], ans[N];
  int n, m, q;

  scanf("%d%d%d", &n, &m, &q);
  n_ = 1;
  while (n_ < q) n_ <<= 1;
  for (int h = 0; h < q; h++) {
    int t;

    scanf("%d", &t);
    if (t == 1) {
      int l, r, k;

      scanf("%d%d%d%d", &l, &r, &cc[h], &k), l--;
      uu[l].push_back({h << 1 | 0, k});
      uu[r].push_back({h << 1 | 0, 0});
    } else if (t == 2) {
      int l, r, k;

      scanf("%d%d%d", &l, &r, &k), l--;
      uu[l].push_back({h << 1 | 1, -k});
      uu[r].push_back({h << 1 | 1, 0});
    } else {
      long long k;
      int i;

      scanf("%d%lld", &i, &k), i--;
      qq[i].push_back({h, k});
    }
  }
  memset(ans, -1, q * sizeof *ans);
  for (int i = 0; i < n; i++) {
    for (auto [h2, k] : uu[i]) {
      int h = h2 >> 1;

      update1(h, k);
      if ((h2 & 1) == 0) update2(h, k);
    }
    for (auto [h, k] : qq[i]) {
      LL x = query1(0, h);

      ans[h] = x < k ? 0 : cc[query3(query2(0, h) - x + k)];
    }
  }
  for (int h = 0; h < q; h++)
    if (ans[h] != -1) printf("%d\n", ans[h]);
}

int main() {
  run();
  return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'void run()':
foodcourt.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d%d%d", &n, &m, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~
foodcourt.cpp:84:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |       scanf("%d%d%d%d", &l, &r, &cc[h], &k), l--;
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:90:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |       scanf("%d%d%d", &l, &r, &k), l--;
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:97:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |       scanf("%d%lld", &i, &k), i--;
      |       ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11