Submission #1138408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138408		duckindog	Food Court (JOI21_foodcourt)	C++17	2 / 100	484 ms	66700 KiB

foodcourt

#include <bits/stdc++.h>

const int N = 250'000 + 10;
int n, m, q;

namespace IT1 { 
  std::vector<long long> lazy[N << 2];

  void shrink(int s) { 
    while (lazy[s].size() >= 2) { 
      if (lazy[s].back() <= 0) { 
        lazy[s].end()[-2] += lazy[s].back();
        lazy[s].pop_back();
        continue;
      }
      if (lazy[s].back() > 0 && lazy[s].end()[-2] >= 0) { 
        lazy[s].end()[-2] += lazy[s].back();
        lazy[s].pop_back();
        continue;
      }
      break;
    }
    if (lazy[s].size() && lazy[s].back() == 0) lazy[s].pop_back();
  }

  void push(int s) { 
    if (!lazy[s].size()) return;
    for (const auto& x : lazy[s]) { 
      lazy[s << 1].push_back(x);    lazy[s << 1 | 1].push_back(x);
      shrink(s << 1);               shrink(s << 1 | 1);
    }
    lazy[s].clear();
  }

  void update(int s, int l, int r, int u, int v, int x) { 
    if (v < l || u > r) return;
    if (u <= l && r <= v) { 
      lazy[s].push_back(x);
      shrink(s);
      return;
    }
    push(s);
    int mid = (l + r) >> 1;
    update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x);
  }
  long long query(int s, int l, int r, int p) { 
    if (p < l || p > r) return 0;
    if (l == r) return lazy[s].size() ? lazy[s].back() : 0;
    push(s);
    int mid = (l + r) >> 1;
    return std::max(query(s << 1, l, mid, p), query(s << 1 | 1, mid + 1, r, p));
  }
}

namespace IT2 { 
  long long f[N << 2];
  void update(int s, int l, int r, int p, int x) { 
    if (p < l || p > r) return;
    if (l == r) { 
      f[s] = std::max(x, 0);
      return;
    }
    int mid = (l + r) >> 1;
    update(s << 1, l, mid, p, x); update(s << 1 | 1, mid + 1, r, p, x);
    f[s] = f[s << 1] + f[s << 1 | 1];
  }

  int query(int s, int l, int r, int p) { 
    if (p < l || p > r) return 0;
    if (l == r) return f[s];
    int mid = (l + r) >> 1;
    return query(s << 1, l, mid, p) + query(s << 1 | 1, mid + 1, r, p);
  }

  std::vector<std::tuple<int, int, int>> segments;
  void collect(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return;
    if (u <= l && r <= v) { 
      segments.emplace_back(s, l, r);
      return;
    }
    int mid = (l + r) >> 1;
    collect(s << 1, l, mid, u, v); collect(s << 1 | 1, mid + 1, r, u, v);
  }
  int walk(int s, int l, int r, long long k) { 
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (f[s << 1 | 1] <= k) return walk(s << 1, l, mid, k - f[s << 1 | 1]);
    return walk(s << 1 | 1, mid + 1, r, k);
  }

  int find(int l, int r, long long k) { 
    segments.clear();
    collect(1, 1, q, l, r);
    std::reverse(segments.begin(), segments.end());

    for (const auto& [s, l, r] : segments) { 
      if (f[s] <= k) k -= f[s];
      else return walk(s, l, r, k);
    }
    assert(false);
  }
}

std::vector<std::tuple<int, int, int>> saveUpdate[N];
std::vector<std::pair<int, int>> saveQuery[N];
int fromGroup[N];

int answer[N];

int32_t main() { 
  std::cin.tie(0)->sync_with_stdio(0);

  std::cin >> n >> m >> q;

  memset(answer, -1, sizeof answer);
  for (int i = 1; i <= q; ++i) { 
    int type; std::cin >> type;
    
    if (type == 1) { 
      int l, r, c, k; std::cin >> l >> r >> c >> k;
      IT1::update(1, 1, n, l, r, k);

      saveUpdate[l].emplace_back(1, i, k);
      saveUpdate[r + 1].emplace_back(0, i, k);

      fromGroup[i] = c;
    } 

    if (type == 2) { 
      int l, r, k; std::cin >> l >> r >> k;
      IT1::update(1, 1, n, l, r, -k);
    }

    if (type == 3) { 
      int p; std::cin >> p;
      long long k; std::cin >> k;
      answer[i] = IT1::query(1, 1, n, p);

      saveQuery[p].push_back({i, k});
    }
  }

  for (int i = 1; i <= n; ++i) { 
    for (const auto& [type, pos, k] : saveUpdate[i]) 
      IT2::update(1, 1, q, pos, type * k);
    
    for (const auto& [idx, k] : saveQuery[i])
      answer[idx] = (answer[idx] < k ? 0 : fromGroup[IT2::find(1, idx, answer[idx] - k)]);
  }

  for (int i = 1; i <= q; ++i)
    if (answer[i] != -1) std::cout << answer[i] << "\n";
}

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