제출 #1138411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138411		duckindog	푸드 코트 (JOI21_foodcourt)	C++17	100 / 100	594 ms	73544 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

#define int long long

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

namespace IT1 { 
  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 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] = max(x, 0ll);
      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);
  }

  vector<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);
    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);
  }
}

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

int answer[N];

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

  cin >> n >> m >> q;

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

    if (type == 3) { 
      int p; cin >> p;
      long long k; 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) cout << answer[i] << "\n";
}

• 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