QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#313458#5264. Wyprzedzaniezfs7320 50ms36688kbC++142.6kb2024-01-24 19:30:442024-01-24 19:30:45

Judging History

你现在查看的是最新测评结果

  • [2024-01-24 19:30:45]
  • 评测
  • 测评结果:0
  • 用时:50ms
  • 内存:36688kb
  • [2024-01-24 19:30:44]
  • 提交

answer

/*
 * _|_|_|_|_|  _|_|_|_|    _|_|_|  _|_|_|_|_|  _|_|_|      _|_|
 *       _|    _|        _|                _|        _|  _|    _|
 *     _|      _|_|_|      _|_|          _|      _|_|        _|
 *   _|        _|              _|      _|            _|    _|
 * _|_|_|_|_|  _|        _|_|_|      _|        _|_|_|    _|_|_|_|
 */

#include<bits/stdc++.h>

const int maxN = 1e5 + 1, maxM = 17;

const long double eps = 1e-8;

long double f[maxM][maxN];
long double ct[maxN], s[maxN], d[maxN], sd[maxN], v[maxN];

inline long double GetV() {
  long double x, y;
  return std::cin >> x >> y, x / y;
}

inline long double Query(int l, int r) {
  if (r < l)
    return 0;

  int k = std::__lg(r - l + 1);
  return std::max(f[k][l], f[k][r - (1 << k) + 1]);
}

int main() {
#ifdef LOCAL
  freopen("task.in", "r", stdin);
  freopen("task.out", "w", stdout);
  freopen("task.err", "w", stderr);
#endif
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, ans = 1;
  long double D, V;
  std::cin >> n >> D, V = GetV();

  for (int i = 1; i <= n; i++) {
    std::cin >> s[i] >> d[i];
    sd[i] = sd[i - 1] + d[i];
    v[i] = GetV();
  }

  std::vector<int> sta;
  sta.emplace_back(n);
  f[0][n] = ct[n] = 1e20;

  auto Catch = [&](int x, int i) {
    long double diff = (s[x] - s[i]) - (sd[x] - sd[i]);
    return diff / (v[i] - v[x]);
  };

  for (int i = n - 1; i >= 1; i--) {
    auto Check = [&](int x) {
      long double t1 = Query(i + 1, x - 1);
      long double t2 = Catch(x, i);
      return t2 - t1 > -eps;
    };

    while (!sta.empty() && v[sta.back()] - v[i] > -eps)
      sta.pop_back();

    if (!sta.empty()) {
      int l = 0, r = int(sta.size() - 1);

      while (l < r) {
        int mid = (l + r) >> 1;

        if (Check(sta[mid]))
          r = mid;
        else
          l = mid + 1;
      }

      ct[i] = Catch(sta[l], i);
    } else
      ct[i] = 1e20;

    f[0][i] = ct[i];
    sta.emplace_back(i);

    for (int j = 1; i + (1 << j) - 1 <= n; j++)
      f[j][i] = std::max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
  }

  for (int i = 1; i < n; i++) {
    long double t = (D + s[i]) / (V - v[i]);

    if (ct[i] <= t)
      continue;

    int l = i + 1, r = n;

    while (l < r) {
      int mid = (l + r + 1) >> 1;

      if (t - Query(i + 1, mid - 1) > -eps)
        l = mid;
      else
        r = mid - 1;
    }

    long double pos = s[l] + t * v[l] - (sd[l] - sd[i]);
    long double diff = pos - (t * v[i] + s[i]);
    ans += diff >= D;
  }

  std::cout << ans << '\n';

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 50ms
memory: 36688kb

input:

100000 9 445 874
1653 9 34 792
2736 336 34 792
21599 862 34 792
23975 188 34 792
41891 401 34 792
62576 193 34 792
74285 567 34 792
78959 2850 34 792
85316 452 34 792
92188 217 34 792
97244 3526 34 792
106804 599 34 792
112500 1352 34 792
120610 581 34 792
123644 213 34 792
123754 16 34 792
125589 4...

output:

99899

result:

wrong answer 1st lines differ - expected: '99905', found: '99899'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #15:

score: 35
Accepted
time: 0ms
memory: 24236kb

input:

1000 5 716 3
632 108 255 785
1891 115 699 140
2143 130 778 315
3409 155 450 486
7330 57 351 675
10955 24 959 657
13151 127 37 429
13903 115 749 82
15213 37 267 276
15906 168 971 23
17068 74 751 600
18435 207 306 662
18493 4 463 490
18882 60 381 293
22184 64 888 663
27168 89 962 190
28751 121 122 898...

output:

527

result:

ok single line: '527'

Test #16:

score: 0
Accepted
time: 0ms
memory: 24408kb

input:

1000 20 917 8
1820 78 441 641
3590 90 486 512
6487 194 536 942
7056 123 266 270
8508 87 130 622
8990 30 654 463
10808 23 741 79
10932 27 228 776
11215 111 458 864
11778 38 751 153
12021 15 321 435
12053 9 162 741
12341 120 496 802
14246 23 431 808
16027 7 508 119
18356 168 362 909
20542 68 465 53
21...

output:

416

result:

ok single line: '416'

Test #17:

score: 0
Accepted
time: 0ms
memory: 24172kb

input:

1000 941 795 2
2446 276 652 673
3067 23 907 79
4023 57 20 189
4076 10 22 364
4263 46 101 752
4508 23 680 464
4777 178 638 58
5426 15 674 162
5537 43 75 564
5882 163 753 662
8162 125 142 638
9026 35 862 797
9117 57 689 398
11859 83 584 712
13277 17 897 881
13389 36 638 525
13790 20 763 810
16538 117 ...

output:

373

result:

ok single line: '373'

Test #18:

score: 0
Accepted
time: 0ms
memory: 24312kb

input:

1000 2625 10 1
477305 370 10 7
1151540 1000 7 10
1893809 12 9 1
3502666 718 4 6
3611320 296 6 6
5699350 260 3 8
8394591 596 3 10
8668961 750 2 4
11183997 981 8 7
13008836 37 10 8
14044159 2729 2 3
14287006 121 1 3
15373289 938 8 1
15724757 1165 1 4
16641191 1541 9 6
16980331 1060 7 3
17356572 4031 8...

output:

176

result:

ok single line: '176'

Test #19:

score: -35
Wrong Answer
time: 2ms
memory: 24188kb

input:

1000 95619 10 1
26818 358 5 2
1122928 1616 6 3
1716816 175 7 10
3119287 836 9 3
3421179 3539 5 8
3570557 357 8 3
3790272 927 3 3
4240818 1211 1 9
5172443 1049 4 9
6239353 52 9 3
6675674 1504 5 3
8167258 66 9 1
9517371 2632 4 9
10547195 527 4 5
11014094 143 3 7
11841288 402 7 4
11968651 1527 5 1
1257...

output:

179

result:

wrong answer 1st lines differ - expected: '178', found: '179'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%