oj.uz

Submission #923758

# Submission time Handle Problem Language Result Execution time Memory
923758 2024-02-07T17:43:41 Z myst6 Sails (IOI07_sails) C++14
100 / 100
 219 ms 6168 KB 
#include <bits/stdc++.h>

using namespace std;

// answer is sum of count[i]*(count[i]-1)/2
// order of masts doesn't matter, so process in ascending order
// choose the K smallest counts to add one to
// start => 2(1)   => 3(2)  => 3(2)  => 4(1)  => 4(3) => 5(3)
// 00000 => 100000 => 11100 => 22100 => 22110 => 32220 => 33321 
// ans = 3+3+3+1=10
// same as the problem i just did but in reverse lol

struct Tag {
  int add; 
  Tag(int _add) : add(_add) {}
  Tag() : add(0) {}
  void apply(Tag &tag) { add += tag.add; }
};

struct Info {
  int m;
  Info(int _m) : m(_m) {}
  Info() : m(1<<30) {}
  void apply(Tag &tag) { m += tag.add; }
  Info combine(Info &other) { return {min(m, other.m)}; }
};

struct Tree {
  vector<Tag> tag;
  vector<Info> info;
  Tree(int size) {
    tag.resize(size*4);
    info.resize(size*4);
  }
  void build(vector<Info> &base, int x, int xl, int xr) {
    if (xl == xr) {
      info[x] = base[xl];
    } else {
      int xm = (xl + xr) / 2;
      build(base, x*2, xl, xm);
      build(base, x*2+1, xm+1, xr);
      info[x] = info[x*2].combine(info[x*2+1]);
    }
  }
  void pushdown(int x) {
    info[x].apply(tag[x]);
    if (x*2 < tag.size()) tag[x*2].apply(tag[x]);
    if (x*2+1 < tag.size()) tag[x*2+1].apply(tag[x]);
    tag[x] = {};
  }
  Info query(int v, int x, int xl, int xr) {
    pushdown(x);
    if (xl == xr) {
      return info[x];
    } else {
      int xm = (xl + xr) / 2;
      if (v <= xm) return query(v, x*2, xl, xm);
      else return query(v, x*2+1, xm+1, xr);
    }
  }
  void update(int l, int r, int x, int xl, int xr, Tag delta) {
    if (l > r) return;
    if (l == xl && r == xr) {
      tag[x].apply(delta);
    } else {
      int xm = (xl + xr) / 2;
      update(l, min(r, xm), x*2, xl, xm, delta);
      update(max(l, xm+1), r, x*2+1, xm+1, xr, delta);
      pushdown(x); pushdown(x*2); pushdown(x*2+1);
      info[x] = info[x*2].combine(info[x*2+1]);
    }
  }
  int find_first(int x, int xl, int xr, function<bool(Info)> pred) {
    pushdown(x);
    if (xl == xr) {
      if (pred(info[x])) return xl;
      else return -1;
    } else {
      pushdown(x*2);
      int xm = (xl + xr) / 2;
      if (pred(info[x*2])) return find_first(x*2, xl, xm, pred);
      else return find_first(x*2+1, xm+1, xr, pred);
    }
  }
};

const int maxh = 100'000;

int main() {
  int N;
  cin >> N;
  vector<pair<int,int>> masts(N);
  for (int i=0; i<N; i++) {
    int H, K;
    cin >> H >> K;
    masts[i] = {H, K};
  }
  sort(masts.begin(), masts.end());
  Tree tree(maxh);
  vector<Info> base(maxh);
  for (int i=0; i<maxh; i++) base[i] = {0};
  tree.build(base, 1, 0, maxh-1);
  function<int(int,int)> first_lte = [&](int v, int end) -> int {
    int idx = tree.find_first(1, 0, maxh-1, [&](Info info) -> bool {
      return info.m <= v;
    });
    if (idx == -1) return end;
    else return idx;
  };
  for (int i=0; i<N; i++) {
    int H = masts[i].first, K = masts[i].second;
    int r = H-1;
    int l = r-K+1;
    int v = tree.query(l, 1, 0, maxh-1).m;
    int vl = first_lte(v, r+1);
    int vr = first_lte(v-1, r+1) - 1;
    int vK = vr-l+1;
    K -= vK;
    if (K > 0) tree.update(r-K+1, r, 1, 0, maxh-1, {+1});
    tree.update(vl, vl+vK-1, 1, 0, maxh-1, {+1});
  }
  vector<int> ct(maxh);
  for (int i=0; i<maxh; i++) ct[i] = tree.query(i, 1, 0, maxh-1).m;
  long long ans = 0;
  for (int i=0; i<maxh; i++) ans += 1LL * ct[i] * (ct[i] - 1) / 2;
  cout << ans << "\n";
  return 0;
}

Compilation message

sails.cpp: In member function 'void Tree::pushdown(int)':
sails.cpp:47:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tag>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     if (x*2 < tag.size()) tag[x*2].apply(tag[x]);
      |         ~~~~^~~~~~~~~~~~
sails.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tag>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     if (x*2+1 < tag.size()) tag[x*2+1].apply(tag[x]);
      |         ~~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4188 KB Output is correct
2 Correct 10 ms 4188 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4188 KB Output is correct
2 Correct 10 ms 4184 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4184 KB Output is correct
2 Correct 10 ms 4188 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4188 KB Output is correct
2 Correct 16 ms 4568 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4240 KB Output is correct
2 Correct 12 ms 4188 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4444 KB Output is correct
2 Correct 65 ms 4808 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 4700 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 5156 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 5724 KB Output is correct
2 Correct 161 ms 5712 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 5996 KB Output is correct
2 Correct 120 ms 5608 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 6128 KB Output is correct
2 Correct 185 ms 6168 KB Output is correct