Submission #937682

#	Time	Username	Problem	Language	Result	Execution time	Memory
937682		nguyentunglam	Food Court (JOI21_foodcourt)	C++17	100 / 100	479 ms	47324 KiB

foodcourt

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 250000 + 10;

int n, m, q;

int ans[N];

vector<tuple<int, int, int, int> > query;

vector<pair<long long, long long> > ask[N];

struct IT1 {
  long long sum[N << 2], pref_sum[N << 2];
  void push(int s, int l, int r) {
    if (!sum[s] && !pref_sum[s]) return;
    if (l == r) return;
    pref_sum[s << 1] = min(pref_sum[s << 1], sum[s << 1] + pref_sum[s]);
    sum[s << 1] += sum[s];
    pref_sum[s << 1 | 1] = min(pref_sum[s << 1 | 1], sum[s << 1 | 1] + pref_sum[s]);
    sum[s << 1 | 1] += sum[s];
    sum[s] = pref_sum[s] = 0;
  }
  void up(int s, int l, int r, int from, int to, long long val) {
    push(s, l, r);
    if (l > to || r < from) return;
    if (from <= l && r <= to) {
      pref_sum[s] = min(pref_sum[s], sum[s] + val);
      sum[s] += val;
      return;
    }
    int mid = l + r >> 1;
    up(s << 1, l, mid, from, to, val);
    up(s << 1 | 1, mid + 1, r, from, to, val);
  }

  pair<long long, long long> get(int s, int l, int r, int pos) {
    push(s, l, r);
    if (l == r) return make_pair(sum[s], pref_sum[s]);
    int mid = l + r >> 1;
    if (pos <= mid) return get(s << 1, l, mid, pos);
    return get(s << 1 | 1, mid + 1, r, pos);
  }
} it1, it2;

struct IT2 {
  long long lazy[N << 2], T[N << 2];

  void push(int s, int l, int r) {
    if (lazy[s] == 0) return;
    T[s] += lazy[s];
    if (l != r) {
      lazy[s << 1] += lazy[s];
      lazy[s << 1 | 1] += lazy[s];
    }
    lazy[s] = 0;
  }

  void up(int s, int l, int r, int from, int to, long long val) {
    push(s, l, r);
    if (l > to || r < from) return;
    if (from <= l && r <= to) {
      lazy[s] = val;
      push(s, l, r);
      return;
    }
    int mid = l + r >> 1;
    up(s << 1, l, mid, from, to, val);
    up(s << 1 | 1, mid + 1, r, from, to, val);
    T[s] = max(T[s << 1], T[s << 1 | 1]);
  }

  int get(int s, int l, int r) {
    push(s, l, r);
    if (l == r) return l;
    int mid = l + r >> 1;
    push(s << 1, l, mid);
    if (T[s << 1] == T[s]) return get(s << 1, l, mid);
    return get(s << 1 | 1, mid + 1, r);
  }
} it3;

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n >> m >> q;

  for(int i = 1; i <= q; i++) {
    int t; cin >> t;
    if (t == 1) {
      int l, r, c, k; cin >> l >> r >> c >> k;
      query.emplace_back(l, r, c, k);
      it1.up(1, 1, n, l, r, k);
      it2.up(1, 1, n, l, r, k);
    }
    if (t == 2) {
      int l, r, k; cin >> l >> r >> k;
      it1.up(1, 1, n, l, r, -k);
    }
    if (t == 3) {
      int a; long long b; cin >> a >> b;
      ans[i] = -1;
      pair<long long, long long> tmp = it1.get(1, 1, n, a);
      long long cur = tmp.first - tmp.second;
      if (cur < b) continue;
      long long total = it2.get(1, 1, n, a).first;
      long long idx = total - cur + b;
      ask[a].emplace_back(idx, i);
//      cout << i << endl;
    }
  }

//  it3.up(1, 1, n, 3, 3, 1);
  for(int i = 1; i <= n; i++) {
    if (ask[i].empty()) {
      it3.up(1, 1, n, i, i, -1e16);
    }
    else {
      sort(all(ask[i]));
      reverse(all(ask[i]));
      it3.up(1, 1, n, i, i, -ask[i].back().first);
    }
  }
//  exit(0);

  int group;

  auto handle = [&] (int pos) {
    long long old = ask[pos].back().first;
    ans[ask[pos].back().second] = group;
    ask[pos].pop_back();
    if (ask[pos].empty()) {
      it3.up(1, 1, n, pos, pos, -1e16);
    }
    else {
      it3.up(1, 1, n, pos, pos, -ask[pos].back().first + old);
    }
  };

  for(auto &[l, r, c, k] : query) {
    group = c;
    it3.up(1, 1, n, l, r, k);
    while (it3.T[1] >= 0) {
      int pos = it3.get(1, 1, n);
      handle(pos);
    }
  }

  for(int i = 1; i <= q; i++) if (ans[i]) {
    cout << max(ans[i], 0) << endl;
  }
}

Compilation message (stderr)

foodcourt.cpp: In member function 'void IT1::up(int, int, int, int, int, long long int)':
foodcourt.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In member function 'std::pair<long long int, long long int> IT1::get(int, int, int, int)':
foodcourt.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In member function 'void IT2::up(int, int, int, int, int, long long int)':
foodcourt.cpp:70:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In member function 'int IT2::get(int, int, int)':
foodcourt.cpp:79:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In function 'int32_t main()':
foodcourt.cpp:92:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:93:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:97:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:98:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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