oj.uz

Submission #1037119

# Submission time Handle Problem Language Result Execution time Memory
1037119 2024-07-28T07:22:33 Z juicy Food Court (JOI21_foodcourt) C++17
21 / 100
 240 ms 45432 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 25e4 + 5;

int n, m, q;
int c[N], res[N];
long long cnt[4 * N];
array<long long, 2> s[4 * N];
vector<pair<long long, int>> Queries[N];
vector<array<int, 3>> events[N];

array<long long, 2> operator + (const array<long long, 2> &lt, const array<long long, 2> &rt) {
  return {max(lt[0] + rt[1], rt[0]), lt[1] + rt[1]};
}

template<class T>
void upd(int i, T x, T *s, int id = 1, int l = 1, int r = q) {
  if (l == r) {
    s[id] = x;
    return;
  }
  int md = (l + r) / 2;
  if (i <= md) {
    upd(i, x, s, id * 2, l, md);
  } else {
    upd(i, x, s, id * 2 + 1, md + 1, r);
  }
  s[id] = s[id * 2] + s[id * 2 + 1];
}

array<long long, 2> qry(int i, int id = 1, int l = 1, int r = q) {
  if (l == r) {
    return s[id];
  }
  int md = (l + r) / 2;
  if (i <= md) {
    return qry(i, id * 2, l, md);
  }
  return s[id * 2] + qry(i, id * 2 + 1, md + 1, r);
}

long long walk(long long k, int id = 1, int l = 1, int r = q) {
  if (l == r) {
    return c[l];
  }
  int md = (l + r) / 2;
  if (k > cnt[id * 2]) {
    return walk(k - cnt[id * 2], id * 2 + 1, md + 1, r);
  }
  return walk(k, id * 2, l, md);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m >> q;
  for (int i = 1; i <= q; ++i) {
    int t; cin >> t;
    if (t == 1) {
      int l, r, k; cin >> l >> r >> c[i] >> k;
      events[l].push_back({i, k, 1});
      events[r + 1].push_back({i, 0, 1});
    } else if (t == 2) {
      int l, r, k; cin >> l >> r >> k;
      events[l].push_back({i, -k, 2});
      events[r + 1].push_back({i, 0, 2});
    } else {
      int p; long long x; cin >> p >> x;
      Queries[p].push_back({x, i});
    }
  }  
  for (int i = 1; i <= n; ++i) {
    for (auto [p, k, t] : events[i]) {
      upd(p, array<long long, 2>{max(0, k), k}, s);
      if (t == 1) {
        upd(p, (long long) k, cnt);
      }
    }
    for (auto [x, id] : Queries[i]) {
      auto dat = qry(id);
      if (dat[0] >= x) {
        res[id] = walk(cnt[1] - dat[0] + x) + 1;
      } else {
        res[id] = 1;
      }
    }
  }
  for (int i = 1; i <= q; ++i) {
    if (res[i]) {
      cout << res[i] - 1 << "\n";
    }
  } 
  return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 22620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 43604 KB Output is correct
2 Correct 142 ms 40788 KB Output is correct
3 Correct 240 ms 44800 KB Output is correct
4 Correct 149 ms 41044 KB Output is correct
5 Correct 159 ms 41072 KB Output is correct
6 Correct 235 ms 45140 KB Output is correct
7 Correct 89 ms 39248 KB Output is correct
8 Correct 99 ms 39176 KB Output is correct
9 Correct 196 ms 44884 KB Output is correct
10 Correct 215 ms 44884 KB Output is correct
11 Correct 192 ms 42992 KB Output is correct
12 Correct 229 ms 45140 KB Output is correct
13 Correct 213 ms 45140 KB Output is correct
14 Correct 214 ms 45140 KB Output is correct
15 Correct 223 ms 45432 KB Output is correct
16 Correct 206 ms 45136 KB Output is correct
17 Correct 214 ms 45140 KB Output is correct
18 Correct 220 ms 44952 KB Output is correct
19 Correct 198 ms 45060 KB Output is correct
20 Correct 209 ms 45140 KB Output is correct
21 Correct 209 ms 45140 KB Output is correct
22 Correct 208 ms 45140 KB Output is correct
23 Correct 206 ms 45144 KB Output is correct
24 Correct 220 ms 45172 KB Output is correct
25 Correct 160 ms 43980 KB Output is correct
26 Correct 166 ms 44372 KB Output is correct
27 Correct 196 ms 43580 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 21844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -