oj.uz

Submission #211844

# Submission time Handle Problem Language Result Execution time Memory
211844 2020-03-21T14:06:57 Z zimpha None (JOI15_walls) C++17
100 / 100
 688 ms 32700 KB 
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

using int64 = long long;

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  std::vector<int> A(n), B(n), idx(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &A[i], &B[i]);
    idx[i] = i;
  }
  std::sort(idx.begin(), idx.end(), [&](int x, int y) {
    return B[x] - A[x] < B[y] - A[y];
  });
  std::vector<int> laser;
  for (int i = 0, x; i < m; ++i) {
    scanf("%d", &x);
    while (laser.size() >= 1 && laser.back() == x) laser.pop_back();
    while (laser.size() >= 2 && ((x > laser.back() && laser.back() > laser[laser.size() - 2]) || (x < laser.back() && laser.back() < laser[laser.size() - 2]))) laser.pop_back();
    laser.push_back(x);
  }
  int64 sum = 0;
  std::set<std::pair<int, int>> len;
  std::set<int> pos;
  m = laser.size();
  for (int i = 0; i < m; ++i) pos.insert(i);
  for (int i = 1; i < m; ++i) {
    len.emplace(std::abs(laser[i] - laser[i - 1]), i - 1);
    sum += std::abs(laser[i] - laser[i - 1]);
  }

  auto remove = [&](int x) {
    auto ix = pos.lower_bound(x);
    if (ix == pos.begin()) {
      auto iy = ix; ++iy;
      len.erase(std::make_pair(std::abs(laser[*iy] - laser[*ix]), *ix));
      sum -= std::abs(laser[*iy] - laser[*ix]);
    } else {
      auto iy = ix; --iy;
      len.erase(std::make_pair(std::abs(laser[*ix] - laser[*iy]), *iy));
      sum -= std::abs(laser[*ix] - laser[*iy]);
      auto iz = ix; ++iz;
      if (iz != pos.end()) {
        len.erase(std::make_pair(std::abs(laser[*iz] - laser[*ix]), *ix));
        sum -= std::abs(laser[*iz] - laser[*ix]);
        len.emplace(std::abs(laser[*iz] - laser[*iy]), *iy);
        sum += std::abs(laser[*iz] - laser[*iy]);
      }
    }
    pos.erase(ix);
  };

  std::vector<int64> ret(n);
  for (auto &x: idx) {
    int bound = B[x] - A[x];
    while (len.size() > 1 && len.begin()->first <= bound) {
      int i = len.begin()->second;
      auto it1 = pos.lower_bound(i);
      auto it2 = it1; ++it2;
      auto it3 = it2; ++it3;
      if (it1 == pos.begin()) remove(i);
      else if (it3 == pos.end()) remove(*it2);
      else {
        remove(i); remove(*it2);
      }
    }
    auto first = pos.begin();
    auto second = first; ++second;
    int64 step = 0;
    if (len.size() >= 2) {
      step += sum - static_cast<int64>(bound) * len.size();
      if (laser[*second] > laser[*first]) step += std::abs(A[x] - laser[*first]);
      else step += std::abs(B[x] - laser[*first]);
    } else {
      int l = A[x], r = B[x];
      if (r < laser[*first]) {
        step += laser[*first] - r;
        l += laser[*first] - r;
        r = laser[*first];
      } else if (l > laser[*first]) {
        step += l - laser[*first];
        r -= l - laser[*first];
        l = laser[*first];
      }
      if (second != pos.end()) {
        if (r < laser[*second]) {
          step += laser[*second] - r;
          l += laser[*second] - r;
          r = laser[*second];
        } else if (l > laser[*second]) {
          step += l - laser[*second];
          r -= l - laser[*second];
          l = laser[*second];
        }
      }
    }
    ret[x] = step;
  }
  for (int i = 0; i < n; ++i) {
    printf("%lld\n", ret[i]);
  }
  return 0;
}

Compilation message

walls.cpp: In function 'int main()':
walls.cpp:10:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~
walls.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &A[i], &B[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
walls.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1024 KB Output is correct
2 Correct 241 ms 15336 KB Output is correct
3 Correct 393 ms 21896 KB Output is correct
4 Correct 346 ms 21868 KB Output is correct
5 Correct 381 ms 21880 KB Output is correct
6 Correct 248 ms 21912 KB Output is correct
7 Correct 27 ms 2040 KB Output is correct
8 Correct 39 ms 2304 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2680 KB Output is correct
2 Correct 337 ms 16360 KB Output is correct
3 Correct 130 ms 10744 KB Output is correct
4 Correct 660 ms 31032 KB Output is correct
5 Correct 435 ms 24428 KB Output is correct
6 Correct 666 ms 30956 KB Output is correct
7 Correct 442 ms 24428 KB Output is correct
8 Correct 680 ms 31084 KB Output is correct
9 Correct 111 ms 9340 KB Output is correct
10 Correct 313 ms 30340 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1024 KB Output is correct
2 Correct 241 ms 15336 KB Output is correct
3 Correct 393 ms 21896 KB Output is correct
4 Correct 346 ms 21868 KB Output is correct
5 Correct 381 ms 21880 KB Output is correct
6 Correct 248 ms 21912 KB Output is correct
7 Correct 27 ms 2040 KB Output is correct
8 Correct 39 ms 2304 KB Output is correct
9 Correct 33 ms 2680 KB Output is correct
10 Correct 337 ms 16360 KB Output is correct
11 Correct 130 ms 10744 KB Output is correct
12 Correct 660 ms 31032 KB Output is correct
13 Correct 435 ms 24428 KB Output is correct
14 Correct 666 ms 30956 KB Output is correct
15 Correct 442 ms 24428 KB Output is correct
16 Correct 680 ms 31084 KB Output is correct
17 Correct 111 ms 9340 KB Output is correct
18 Correct 313 ms 30340 KB Output is correct
19 Correct 484 ms 26092 KB Output is correct
20 Correct 685 ms 32700 KB Output is correct
21 Correct 450 ms 26092 KB Output is correct
22 Correct 604 ms 29972 KB Output is correct
23 Correct 488 ms 25964 KB Output is correct
24 Correct 688 ms 32620 KB Output is correct
25 Correct 154 ms 11640 KB Output is correct
26 Correct 174 ms 12296 KB Output is correct
27 Correct 349 ms 32380 KB Output is correct