oj.uz

Submission #625098

# Submission time Handle Problem Language Result Execution time Memory
625098 2022-08-09T10:55:16 Z juancarlovieri Distributing Candies (IOI21_candies) C++17
29 / 100
 1336 ms 25204 KB 
#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;


#define int long long
#define sl i + 1
#define sr i + (sm - ss + 1) * 2
#define sm (ss + se) / 2
#define block 350

int pend[400005], tree[400005], pend2[400005];
int pre[200005];

void push(int i, int ss, int se) {
  // assert(!(pend[i] and pend2[i]));
  if (pend2[i] == 1) {
    tree[i] = 0;
    if (ss != se) {
      pend2[sl] = 1;
      pend2[sr] = 1;
      pend[sl] = 0;
      pend[sr] = 0;
    }
    pend2[i] = 0;
  }

  if (pend2[i] == 2) {
    tree[i] = pre[se];
    if (ss != se) {
      pend2[sl] = 2;
      pend2[sr] = 2;
      pend[sl] = 0;
      pend[sr] = 0;
    }
    pend2[i] = 0;
  }

  if (pend[i]) {
    tree[i] += pend[i];
    if (ss != se) {
      pend[sl] += pend[i];
      pend[sr] += pend[i];
    }
    pend[i] = 0;
  }
}

void upd(int l, int r, int val, int ss = 0, int se = 200000, int i = 0) {
  push(i, ss, se);
  if (ss > se or l > se or r < ss) return;
  if (ss >= l and se <= r) {
    pend[i] += val;
    // cout << i << endl;
    push(i, ss, se);
    return;
  }
  upd(l, r, val, ss, sm, sl);
  upd(l, r, val, sm + 1, se, sr);

  tree[i] = max(tree[sl], tree[sr]);
}


void forc(int l, int r, int val, int ss = 0, int se = 200000, int i = 0) {
  push(i, ss, se);
  if (ss > se or l > se or r < ss) return;
  if (ss >= l and se <= r) {
    pend2[i] = val;
    push(i, ss, se);
    return;
  }
  forc(l, r, val, ss, sm, sl);
  forc(l, r, val, sm + 1, se, sr);

  tree[i] = max(tree[sl], tree[sr]);
}

int get(int l, int r, int ss = 0, int se = 200000, int i = 0) {
  push(i, ss, se);
  if (ss > se or ss > r or se < l) return 0;
  if (ss >= l and se <= r) return tree[i];
  return max(get(l, r, ss, sm, sl), get(l, r, sm + 1, se, sr));
}


std::vector<signed> distribute_candies(std::vector<signed> c, std::vector<signed> l,
                                    std::vector<signed> r, std::vector<signed> v) {
  int n = c.size();
  int q = l.size();
  vector<pair<int, int>> all;
  for (int i = 0; i < n; ++i) all.push_back({c[i], i});
  sort(all.begin(), all.end());

  pre[0] = all[0].first;
  for (int i = 1; i < n; ++i) {
    pre[i] = all[i].first;
    // pre[i] = pre[i - 1] + all[i].first;
  }

  // for (int i = 0; i < n; ++i) {
  //   cout << pre[i] << ' ';
  // }
  // cout << endl;

  for (int i = 0; i < q; ++i) {
    int x = v[i];
    if (x > 0) {
      int lo = 0, hi = n - 1;
      while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (get(0, mid) + x < all[mid].first) hi = mid - 1;
        else lo = mid + 1;
      }
      // hi = -1;
      if (hi != -1) {
        forc(0, hi, 2);
      }
      // cout << hi << endl;
      upd(hi + 1, n - 1, x);
      // cout << get(0, n - 1) << endl;
    } else {
      x *= -1;
      int lo = 0, hi = n - 1;
      while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (get(0, mid) > x) {
          hi = mid - 1;
        } else {
          lo = mid + 1;
        }
      }
      // cout << hi << endl;
      // hi = -1;
      if (hi != -1) {
        forc(0, hi, 1);
      }
      upd(hi + 1, n - 1, -x);
    }
  }

  std::vector<signed> s(n);
  for (int i = 0; i < n; ++i) {
    s[all[i].second] = get(i, i);
  }
  return s;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 670 ms 5772 KB Output is correct
4 Correct 162 ms 16844 KB Output is correct
5 Correct 1318 ms 22068 KB Output is correct
6 Correct 1336 ms 22976 KB Output is correct
7 Correct 1319 ms 22624 KB Output is correct
8 Correct 1237 ms 24268 KB Output is correct
9 Correct 912 ms 25204 KB Output is correct

Subtask #5
0 / 33.0

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