oj.uz

Submission #420472

# Submission time Handle Problem Language Result Execution time Memory
420472 2021-06-08T11:40:08 Z juancarlovieri Autobahn (COI21_autobahn) C++17
100 / 100
 368 ms 26864 KB 
#include <bits/stdc++.h>
using namespace std;

#define kath ash
#define int long long

signed main() {
  int n, k, x;
  cin >> n >> k >> x;
  vector<int> l(n), t(n), r(n), events;
  for (int i = 0; i < n; ++i) {
    cin >> l[i] >> t[i] >> r[i];
    events.push_back(l[i]);
    events.push_back(r[i]);
    events.push_back(r[i] + 1);
    events.push_back(r[i] - x);
    events.push_back((l[i] + t[i] - 1));
    events.push_back(l[i] - x + 1);
    events.push_back((l[i] + t[i] - 1) + 1);
    events.push_back(r[i] - x + 1);
    events.push_back((l[i] + t[i] - 1) - x + 1);
    events.push_back((l[i] + t[i] - 1) - x);
  }
  sort(events.begin(), events.end());
  events.resize(unique(events.begin(), events.end()) - events.begin());
  events.push_back(1000000000000);
  vector<int> bad(events.size()), num(events.size());
  for (int i = 0; i < n; ++i) {
    int j = lower_bound(events.begin(), events.end(), l[i]) - events.begin();
    ++num[j];
    j = lower_bound(events.begin(), events.end(), r[i] + 1) - events.begin();
    --num[j];
  }
  for (int i = 0; i < n; ++i) {
    if (l[i] + t[i] - 1 <= r[i]) {
      int j = lower_bound(events.begin(), events.end(), l[i] + t[i]) - events.begin();
      bad[j]++;
      j = lower_bound(events.begin(), events.end(), r[i] + 1) - events.begin();
      bad[j]--;
    }
  }
  for (int i = 1; i < events.size(); ++i) num[i] += num[i - 1], bad[i] += bad[i - 1];
  int curl = events[0], curr = -1000000000000, val = 0, j = 0, ans = 0;
  int goal = 0;
  for (int i = 0; i + 1 < events.size(); i++) {
    curl = events[i];
    if (curr <= curl) {
      curr = curl;
      val = ((num[i] >= k)) * bad[i];
      j = i + 1;
    } else {
      val -= (events[i] - events[i - 1]) * (bad[i - 1]) * (num[i - 1] >= k);
    }
    while (1) {
      if (events[j] > x + curl - 1) {
        val += (bad[j - 1]) * (num[j - 1] >= k) * (curl + x - 1 - curr);
        curr = curl + x - 1;
        break;
      } else {
        val += (bad[j - 1]) * (num[j - 1] >= k) *  (events[j] - 1 - curr);
        curr = events[j] - 1;
        ++j;
      }
    }

    if (val > ans) {
      ans = val;
      goal = events[i];
    }
  }
  cout << ans << endl;
}

Compilation message

autobahn.cpp: In function 'int main()':
autobahn.cpp:42:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int i = 1; i < events.size(); ++i) num[i] += num[i - 1], bad[i] += bad[i - 1];
      |                   ~~^~~~~~~~~~~~~~~
autobahn.cpp:45:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int i = 0; i + 1 < events.size(); i++) {
      |                   ~~~~~~^~~~~~~~~~~~~~~
autobahn.cpp:44:7: warning: variable 'goal' set but not used [-Wunused-but-set-variable]
   44 |   int goal = 0;
      |       ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 464 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 464 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 428 KB Output is correct
20 Correct 2 ms 460 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 464 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 464 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 428 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 365 ms 26612 KB Output is correct
22 Correct 368 ms 26784 KB Output is correct
23 Correct 348 ms 26864 KB Output is correct
24 Correct 334 ms 26836 KB Output is correct
25 Correct 339 ms 26720 KB Output is correct
26 Correct 332 ms 26808 KB Output is correct
27 Correct 326 ms 26764 KB Output is correct
28 Correct 336 ms 26748 KB Output is correct
29 Correct 329 ms 26748 KB Output is correct