提出 #8301236 - AtCoder Grand Contest 040

コンテスト時間: 2019-11-04 00:00:00+0900 ~ 2019-11-04 02:30:00+0900 (150分) AtCoderホームへ戻る

提出 #8301236

ソースコード拡げる

#include <bits/stdc++.h>

using namespace std;

#define range(i, m, n) for(int i = m; i < n; i++)
#define husk(i, m, n) for(int i = m; i > n; i--)

class segtree {
  public:
  struct node {

    long long sum = 0;
    int p = 0;

    void apply(int l, int r, int v) {
      assert(l == r);
      if(v > 0) {
        sum = v;
        p = 1;
        return;
      }
      sum = 0;
      p = 0;
    }
  };

  node unite(const node &a, const node &b) const {
    node res;
    res.sum = a.sum + b.sum;
    res.p = a.p + b.p;
    return res;
  }

  inline void push(int x, int l, int r) {

  }

  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }

  int n;
  vector<node> tree;

  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M, typename... T>
  void build(int x, int l, int r, const vector<M> &v, const T&... t) {
    if (l == r) {
      tree[x].apply(l, r, v[l], t...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v, t...);
    build(z, y + 1, r, v, t...);
    pull(x, z);
  }

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }

  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M&... v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }

  int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }

  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }

  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }

  template <typename M, typename... T>
  segtree(const vector<M> &v, const T&... t) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v, t...);
  }

  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }

  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }

  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }

};

int n;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  vector<int> a(n);
  vector<int> b(n);
  range(i, 0, n) {
    cin >> a[i] >> b[i];
  }
  long long cur = 0;
  long long sum = 0;
  vector<int> id;
  vector<int> pr;
  range(i, 0, n) {
    if(b[i] >= a[i]) {
      cur += b[i] - a[i];
      pr.push_back(b[i]);
    } else id.push_back(i);
  }
  if(cur == 0) {
    cout << "0 1\n";
    return 0;
  }
  sort(pr.begin(), pr.end());
  int pos = 0;
  while(sum + pr[pos] <= cur) {
    sum += pr[pos];
    pos++;
  }
  long long u = 1LL * pos * pr[pos] + cur - sum;
  long long v = pr[pos];
  if(id.empty()) {
    v *= n;
    long long g = __gcd(u, v);
    cout << u / g << " " << v / g;
    return 0;
  }
  sort(id.begin(), id.end(), [&](int x, int y){return a[x] < a[y];});
  vector<int> _a, _b;
  map<int, vector<int>> pb;
  range(i, 0, (int) id.size()) {
    _a.push_back(a[id[i]]);
    _b.push_back(b[id[i]]);
    if(b[id[i]] < pr[pos]) pb[b[id[i]]].push_back(i);
  }
  vector<long long> pref(pr.size());
  range(i, 0, (int) pr.size()) {
    pref[i] = pr[i];
    if(i > 0) pref[i] += pref[i - 1];
  }
  segtree sa(_a);
  segtree sb(_b);
  while(!pb.empty()) {
    auto it = prev(pb.end());
    int x = it->first;
    int y = it->second.front();
    sa.modify(y, y, 0);
    sb.modify(y, y, 0);
    long long c = cur + x - _a[y];
    int p = lower_bound(pr.begin(), pr.end(), x) - pr.begin();
    long long csum = c - (p > 0 ? pref[p - 1] : 0);
    if(csum <= 0) {
      for(int i : it->second) {
        sa.modify(i, i, 0);
        sb.modify(i, i, 0);
      }
      pb.erase(it);
      continue;
    }
    
    long long ss = 0;
    int sz = sa.find_first(0, id.size() - 1, [&](const segtree::node z){
      if(z.sum + ss >= csum) return true;
      ss += z.sum;
      return false;
    });
    if(sz == -1) sz = id.size() - 1;
    else sz--;
    segtree::node s;
    segtree::node d;
    if(sz >= 0) {
      s = sa.get(0, sz);
      d = sb.get(0, sz);
    }
    
    long long zsum = (p > 0 ? pref[p - 1] : 0LL) + d.sum;
    c += d.sum - s.sum;
    assert(zsum < c);
    long long su, sv;
    if(zsum + x > c) {
      su = 1LL * (p + s.p) * x + c - zsum;
      sv = x;
    } else {
      int ap = upper_bound(pref.begin(), pref.end(), c - d.sum - x) - pref.begin();
      assert(ap >= p);
      su = 1LL * (ap + s.p + 1) * pr[ap] + c - d.sum - x - (ap > 0 ? pref[ap - 1] : 0);
      sv = pr[ap];
    }
    
    if(su / sv > u / v || (su / sv == u / v && (su % sv) * v > (u % v) * sv)) {
      u = su;
      v = sv;
    }
    for(int i : it->second) {
      sa.modify(i, i, 0);
      sb.modify(i, i, 0);
    }
    pb.erase(it);
  }
  v *= n;
  long long g = __gcd(u, v);
  u /= g; v /= g;
  cout << u << " " << v;
  return 0;
}

提出情報

提出日時	2019-11-05 20:39:25+0900
問題	D - Balance Beam
ユーザ	KanonNakagawa
言語	C++14 (GCC 5.4.1)
得点	0
コード長	8104 Byte
結果	WA
実行時間	127 ms
メモリ	14840 KiB

ジャッジ結果

セット名

Sample

All

得点 / 配点

0 / 0

0 / 1100

結果

× 4

AC	× 28
WA	× 16

セット名	テストケース
Sample	00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 00-sample-04.txt
All	00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 00-sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt

ケース名	結果	実行時間	メモリ
00-sample-01.txt	AC	1 ms	256 KiB
00-sample-02.txt	AC	1 ms	256 KiB
00-sample-03.txt	AC	1 ms	256 KiB
00-sample-04.txt	AC	1 ms	256 KiB
01-01.txt	AC	1 ms	256 KiB
01-02.txt	WA	44 ms	5248 KiB
01-03.txt	WA	81 ms	9180 KiB
01-04.txt	WA	40 ms	4864 KiB
01-05.txt	WA	59 ms	6784 KiB
01-06.txt	WA	38 ms	4608 KiB
01-07.txt	WA	17 ms	2304 KiB
01-08.txt	WA	26 ms	3200 KiB
01-09.txt	WA	94 ms	10492 KiB
01-10.txt	AC	17 ms	2796 KiB
01-11.txt	AC	30 ms	4692 KiB
01-12.txt	AC	57 ms	8744 KiB
01-13.txt	AC	57 ms	9012 KiB
01-14.txt	AC	30 ms	4824 KiB
01-15.txt	AC	11 ms	2036 KiB
01-16.txt	AC	57 ms	8620 KiB
01-17.txt	AC	10 ms	1664 KiB
01-18.txt	AC	23 ms	3684 KiB
01-19.txt	AC	6 ms	640 KiB
01-20.txt	WA	96 ms	10620 KiB
01-21.txt	WA	95 ms	10564 KiB
01-22.txt	WA	95 ms	10576 KiB
01-23.txt	WA	98 ms	10620 KiB
01-24.txt	WA	96 ms	10596 KiB
01-25.txt	WA	95 ms	10576 KiB
01-26.txt	WA	95 ms	10576 KiB
01-27.txt	WA	95 ms	10572 KiB
01-28.txt	AC	58 ms	9000 KiB
01-29.txt	AC	59 ms	9004 KiB
01-30.txt	AC	59 ms	9016 KiB
01-31.txt	AC	58 ms	9124 KiB
01-32.txt	AC	58 ms	9132 KiB
01-33.txt	AC	58 ms	9008 KiB
01-34.txt	AC	59 ms	9008 KiB
01-35.txt	AC	59 ms	9128 KiB
01-36.txt	AC	59 ms	9008 KiB
01-37.txt	AC	22 ms	1660 KiB
01-38.txt	AC	86 ms	10692 KiB
01-39.txt	AC	103 ms	12880 KiB
01-40.txt	AC	127 ms	14840 KiB