oj.uz

Submission #937064

# Submission time Handle Problem Language Result Execution time Memory
937064 2024-03-03T10:30:57 Z rxlfd314 New Home (APIO18_new_home) C++17
57 / 100
 5000 ms 330320 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using ari4 = array<int, 4>;
 
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
 
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
 
constexpr int mxN = 300000;
int N, K, Q;
vt<int> cmp;
 
struct ST {
  priority_queue<int> st[mxN<<1], die[mxN<<1];
  void kill(int i) {
    while (size(st[i]) && size(die[i]) && st[i].top() == die[i].top())
      st[i].pop(), die[i].pop();
  }
  void insert(int ql, int qr, int v) {
    for (ql += size(cmp), qr += size(cmp) + 1; ql < qr; ql >>= 1, qr >>= 1) {
      if (ql & 1)
        st[ql++].push(v);
      if (qr & 1)
        st[--qr].push(v);
    }
  }
  void erase(int ql, int qr, int v) {
    for (ql += size(cmp), qr += size(cmp) + 1; ql < qr; ql >>= 1, qr >>= 1) {
      if (ql & 1)
        die[ql++].push(v);
      if (qr & 1)
        die[--qr].push(v);
    }
  }
  int qry(int i) {
    int res = INT_MIN;
    for (i += size(cmp); i > 0; i >>= 1)
      kill(i), res = max(res, size(st[i]) ? st[i].top() : res);
    return res;
  }
} st_left, st_right;

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N >> K >> Q;
  vt<ari4> events;
  FOR(i, 0, N-1) {
    int x, t, a, b;
    cin >> x >> t >> a >> b, t--;
    events.push_back({a, 1, x, t}); // time, (0 = insert, 1 = remove, 2 = is year), location, type
    events.push_back({b+1, 0, x, t});
  }
  FOR(i, 0, Q-1) {
    int year, x;
    cin >> x >> year;
    events.push_back({year, 2, x, i}); // time, is year, location, query index
    cmp.push_back(x);
  }
  sort(all(cmp));
  cmp.erase(unique(all(cmp)), end(cmp));
  sort(all(events), greater<ari4>());

  auto ind = [&](int v) {
    return lower_bound(all(cmp), v) - begin(cmp);
  };
  auto erase = [&](int l, int r) {
    assert(l + r + 1 >= 0);
    int m = l + r + 1 >> 1;
    int li = ind(l), ri = ind(r), mi = ind(m);
    ri -= cmp[ri] > r;
    if (mi - 1 >= li)
      st_left.erase(li, mi-1, -l); 
    if (ri >= mi)
      st_right.erase(mi, ri, r);
  };
  auto insert = [&](int l, int r) {
    assert(l + r + 1 >= 0);
    int m = l + r + 1 >> 1;
    int li = ind(l), ri = ind(r), mi = ind(m);
    ri -= cmp[ri] > r;
    if (mi - 1 >= li)
      st_left.insert(li, mi-1, -l);
    if (ri >= mi)
      st_right.insert(mi, ri, r);
  };

  vt<int> ans(Q), present(K);
  vt<map<int, int>> positions(K);
  int present_cnt = 0;
  for (auto &[t, is_query, x, type] : events) {
    if (is_query == 2) {
      if (present_cnt < K) {
        ans[type] = -1;
        continue;
      }
      int i = ind(x);
      int l = st_left.qry(i);
      if (l != INT_MIN)
        l = -l;
      else
        l = x;
      int r = st_right.qry(i);
      l = min(l, x);
      r = max(r, x);
      ans[type] = max(r - x, x - l);
#ifdef DEBUG
      cout << "at time " << t << " answer for " << x << " is:\n";
      cout << "L: " << l << '\n';
      cout << "R: " << r << '\n';
#endif
    } else if (is_query) {
      auto &xs = positions[type];
      if (xs[x] == 1) {
        auto it = xs.find(x);
        int l = it != begin(xs) ? prev(it)->first : -1;
        int r = next(it) != end(xs) ? next(it)->first : INT_MAX;
        xs.erase(it);
        if (l >= 0)
          erase(l, x);
        else
          erase(-x, x);
        if (r < INT_MAX)
          erase(x, r); 
        else
          erase(x, INT_MAX - x - 1);

        if (l >= 0 && r < INT_MAX)
          insert(l, r);
        else if (l >= 0)
          insert(l, INT_MAX - l - 1);
        else if (r < INT_MAX)
          insert(-r, r);
      } else {
        xs[x]--;
      }
      present_cnt -= --present[type] == 0;
    } else {
      auto &xs = positions[type];
      if (xs[x])
        xs[x]++;
      else {
        xs[x] = 1;
        auto it = xs.find(x);
        int l = it != begin(xs) ? prev(it)->first : -1;
        int r = next(it) != end(xs) ? next(it)->first : INT_MAX;
        if (l >= 0 && r < INT_MAX)
          erase(l, r);
        else if (l >= 0)
          erase(l, INT_MAX - l - 1);
        else if (r < INT_MAX)
          erase(-r, r);

        if (l >= 0)
          insert(l, x);
        else
          insert(-x, x);
        if (r < INT_MAX)
          insert(x, r);
        else
          insert(x, INT_MAX - x - 1);
      }
      present_cnt += ++present[type] == 1;
    }
  }

  for (int &i : ans)
    cout << i << '\n';
}

Compilation message

new_home.cpp: In lambda function:
new_home.cpp:79:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~
new_home.cpp: In lambda function:
new_home.cpp:89:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 75512 KB Output is correct
2 Correct 23 ms 75352 KB Output is correct
3 Correct 22 ms 75356 KB Output is correct
4 Correct 22 ms 75608 KB Output is correct
5 Correct 21 ms 75472 KB Output is correct
6 Correct 22 ms 75864 KB Output is correct
7 Correct 22 ms 75612 KB Output is correct
8 Correct 24 ms 75532 KB Output is correct
9 Correct 21 ms 75612 KB Output is correct
10 Correct 23 ms 75612 KB Output is correct
11 Correct 21 ms 75612 KB Output is correct
12 Correct 25 ms 75608 KB Output is correct
13 Correct 21 ms 75612 KB Output is correct
14 Correct 22 ms 75540 KB Output is correct
15 Correct 22 ms 75608 KB Output is correct
16 Correct 22 ms 75612 KB Output is correct
17 Correct 24 ms 75768 KB Output is correct
18 Correct 21 ms 75556 KB Output is correct
19 Correct 25 ms 75608 KB Output is correct
20 Correct 23 ms 75612 KB Output is correct
21 Correct 21 ms 75528 KB Output is correct
22 Correct 21 ms 75612 KB Output is correct
23 Correct 22 ms 75612 KB Output is correct
24 Correct 22 ms 75608 KB Output is correct
25 Correct 22 ms 75612 KB Output is correct
26 Correct 23 ms 75512 KB Output is correct
27 Correct 21 ms 75612 KB Output is correct
28 Correct 24 ms 75612 KB Output is correct
29 Correct 23 ms 75608 KB Output is correct
30 Correct 21 ms 75612 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 75512 KB Output is correct
2 Correct 23 ms 75352 KB Output is correct
3 Correct 22 ms 75356 KB Output is correct
4 Correct 22 ms 75608 KB Output is correct
5 Correct 21 ms 75472 KB Output is correct
6 Correct 22 ms 75864 KB Output is correct
7 Correct 22 ms 75612 KB Output is correct
8 Correct 24 ms 75532 KB Output is correct
9 Correct 21 ms 75612 KB Output is correct
10 Correct 23 ms 75612 KB Output is correct
11 Correct 21 ms 75612 KB Output is correct
12 Correct 25 ms 75608 KB Output is correct
13 Correct 21 ms 75612 KB Output is correct
14 Correct 22 ms 75540 KB Output is correct
15 Correct 22 ms 75608 KB Output is correct
16 Correct 22 ms 75612 KB Output is correct
17 Correct 24 ms 75768 KB Output is correct
18 Correct 21 ms 75556 KB Output is correct
19 Correct 25 ms 75608 KB Output is correct
20 Correct 23 ms 75612 KB Output is correct
21 Correct 21 ms 75528 KB Output is correct
22 Correct 21 ms 75612 KB Output is correct
23 Correct 22 ms 75612 KB Output is correct
24 Correct 22 ms 75608 KB Output is correct
25 Correct 22 ms 75612 KB Output is correct
26 Correct 23 ms 75512 KB Output is correct
27 Correct 21 ms 75612 KB Output is correct
28 Correct 24 ms 75612 KB Output is correct
29 Correct 23 ms 75608 KB Output is correct
30 Correct 21 ms 75612 KB Output is correct
31 Correct 1086 ms 115788 KB Output is correct
32 Correct 73 ms 80128 KB Output is correct
33 Correct 759 ms 98436 KB Output is correct
34 Correct 1111 ms 115148 KB Output is correct
35 Correct 981 ms 109856 KB Output is correct
36 Correct 722 ms 97764 KB Output is correct
37 Correct 522 ms 99188 KB Output is correct
38 Correct 380 ms 93584 KB Output is correct
39 Correct 364 ms 95396 KB Output is correct
40 Correct 327 ms 93592 KB Output is correct
41 Correct 777 ms 103004 KB Output is correct
42 Correct 724 ms 109036 KB Output is correct
43 Correct 65 ms 80948 KB Output is correct
44 Correct 786 ms 102256 KB Output is correct
45 Correct 780 ms 98648 KB Output is correct
46 Correct 826 ms 96796 KB Output is correct
47 Correct 337 ms 104360 KB Output is correct
48 Correct 364 ms 101208 KB Output is correct
49 Correct 435 ms 105832 KB Output is correct
50 Correct 414 ms 110912 KB Output is correct
51 Correct 493 ms 103620 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3630 ms 313476 KB Output is correct
2 Correct 2545 ms 251316 KB Output is correct
3 Correct 1451 ms 240900 KB Output is correct
4 Correct 3216 ms 302612 KB Output is correct
5 Correct 2087 ms 247928 KB Output is correct
6 Correct 2430 ms 250188 KB Output is correct
7 Correct 1438 ms 235148 KB Output is correct
8 Correct 3250 ms 310304 KB Output is correct
9 Correct 3426 ms 286616 KB Output is correct
10 Correct 2924 ms 280864 KB Output is correct
11 Correct 2354 ms 258304 KB Output is correct
12 Correct 2345 ms 262352 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5094 ms 330320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 75512 KB Output is correct
2 Correct 23 ms 75352 KB Output is correct
3 Correct 22 ms 75356 KB Output is correct
4 Correct 22 ms 75608 KB Output is correct
5 Correct 21 ms 75472 KB Output is correct
6 Correct 22 ms 75864 KB Output is correct
7 Correct 22 ms 75612 KB Output is correct
8 Correct 24 ms 75532 KB Output is correct
9 Correct 21 ms 75612 KB Output is correct
10 Correct 23 ms 75612 KB Output is correct
11 Correct 21 ms 75612 KB Output is correct
12 Correct 25 ms 75608 KB Output is correct
13 Correct 21 ms 75612 KB Output is correct
14 Correct 22 ms 75540 KB Output is correct
15 Correct 22 ms 75608 KB Output is correct
16 Correct 22 ms 75612 KB Output is correct
17 Correct 24 ms 75768 KB Output is correct
18 Correct 21 ms 75556 KB Output is correct
19 Correct 25 ms 75608 KB Output is correct
20 Correct 23 ms 75612 KB Output is correct
21 Correct 21 ms 75528 KB Output is correct
22 Correct 21 ms 75612 KB Output is correct
23 Correct 22 ms 75612 KB Output is correct
24 Correct 22 ms 75608 KB Output is correct
25 Correct 22 ms 75612 KB Output is correct
26 Correct 23 ms 75512 KB Output is correct
27 Correct 21 ms 75612 KB Output is correct
28 Correct 24 ms 75612 KB Output is correct
29 Correct 23 ms 75608 KB Output is correct
30 Correct 21 ms 75612 KB Output is correct
31 Correct 1086 ms 115788 KB Output is correct
32 Correct 73 ms 80128 KB Output is correct
33 Correct 759 ms 98436 KB Output is correct
34 Correct 1111 ms 115148 KB Output is correct
35 Correct 981 ms 109856 KB Output is correct
36 Correct 722 ms 97764 KB Output is correct
37 Correct 522 ms 99188 KB Output is correct
38 Correct 380 ms 93584 KB Output is correct
39 Correct 364 ms 95396 KB Output is correct
40 Correct 327 ms 93592 KB Output is correct
41 Correct 777 ms 103004 KB Output is correct
42 Correct 724 ms 109036 KB Output is correct
43 Correct 65 ms 80948 KB Output is correct
44 Correct 786 ms 102256 KB Output is correct
45 Correct 780 ms 98648 KB Output is correct
46 Correct 826 ms 96796 KB Output is correct
47 Correct 337 ms 104360 KB Output is correct
48 Correct 364 ms 101208 KB Output is correct
49 Correct 435 ms 105832 KB Output is correct
50 Correct 414 ms 110912 KB Output is correct
51 Correct 493 ms 103620 KB Output is correct
52 Correct 296 ms 106672 KB Output is correct
53 Correct 330 ms 105388 KB Output is correct
54 Correct 597 ms 120796 KB Output is correct
55 Correct 608 ms 109380 KB Output is correct
56 Correct 550 ms 109976 KB Output is correct
57 Correct 834 ms 108340 KB Output is correct
58 Correct 576 ms 110932 KB Output is correct
59 Correct 488 ms 112272 KB Output is correct
60 Correct 731 ms 112568 KB Output is correct
61 Correct 82 ms 88480 KB Output is correct
62 Correct 319 ms 106828 KB Output is correct
63 Correct 477 ms 115828 KB Output is correct
64 Correct 558 ms 117024 KB Output is correct
65 Correct 672 ms 116696 KB Output is correct
66 Correct 747 ms 110204 KB Output is correct
67 Correct 144 ms 89240 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 75512 KB Output is correct
2 Correct 23 ms 75352 KB Output is correct
3 Correct 22 ms 75356 KB Output is correct
4 Correct 22 ms 75608 KB Output is correct
5 Correct 21 ms 75472 KB Output is correct
6 Correct 22 ms 75864 KB Output is correct
7 Correct 22 ms 75612 KB Output is correct
8 Correct 24 ms 75532 KB Output is correct
9 Correct 21 ms 75612 KB Output is correct
10 Correct 23 ms 75612 KB Output is correct
11 Correct 21 ms 75612 KB Output is correct
12 Correct 25 ms 75608 KB Output is correct
13 Correct 21 ms 75612 KB Output is correct
14 Correct 22 ms 75540 KB Output is correct
15 Correct 22 ms 75608 KB Output is correct
16 Correct 22 ms 75612 KB Output is correct
17 Correct 24 ms 75768 KB Output is correct
18 Correct 21 ms 75556 KB Output is correct
19 Correct 25 ms 75608 KB Output is correct
20 Correct 23 ms 75612 KB Output is correct
21 Correct 21 ms 75528 KB Output is correct
22 Correct 21 ms 75612 KB Output is correct
23 Correct 22 ms 75612 KB Output is correct
24 Correct 22 ms 75608 KB Output is correct
25 Correct 22 ms 75612 KB Output is correct
26 Correct 23 ms 75512 KB Output is correct
27 Correct 21 ms 75612 KB Output is correct
28 Correct 24 ms 75612 KB Output is correct
29 Correct 23 ms 75608 KB Output is correct
30 Correct 21 ms 75612 KB Output is correct
31 Correct 1086 ms 115788 KB Output is correct
32 Correct 73 ms 80128 KB Output is correct
33 Correct 759 ms 98436 KB Output is correct
34 Correct 1111 ms 115148 KB Output is correct
35 Correct 981 ms 109856 KB Output is correct
36 Correct 722 ms 97764 KB Output is correct
37 Correct 522 ms 99188 KB Output is correct
38 Correct 380 ms 93584 KB Output is correct
39 Correct 364 ms 95396 KB Output is correct
40 Correct 327 ms 93592 KB Output is correct
41 Correct 777 ms 103004 KB Output is correct
42 Correct 724 ms 109036 KB Output is correct
43 Correct 65 ms 80948 KB Output is correct
44 Correct 786 ms 102256 KB Output is correct
45 Correct 780 ms 98648 KB Output is correct
46 Correct 826 ms 96796 KB Output is correct
47 Correct 337 ms 104360 KB Output is correct
48 Correct 364 ms 101208 KB Output is correct
49 Correct 435 ms 105832 KB Output is correct
50 Correct 414 ms 110912 KB Output is correct
51 Correct 493 ms 103620 KB Output is correct
52 Correct 3630 ms 313476 KB Output is correct
53 Correct 2545 ms 251316 KB Output is correct
54 Correct 1451 ms 240900 KB Output is correct
55 Correct 3216 ms 302612 KB Output is correct
56 Correct 2087 ms 247928 KB Output is correct
57 Correct 2430 ms 250188 KB Output is correct
58 Correct 1438 ms 235148 KB Output is correct
59 Correct 3250 ms 310304 KB Output is correct
60 Correct 3426 ms 286616 KB Output is correct
61 Correct 2924 ms 280864 KB Output is correct
62 Correct 2354 ms 258304 KB Output is correct
63 Correct 2345 ms 262352 KB Output is correct
64 Execution timed out 5094 ms 330320 KB Time limit exceeded
65 Halted 0 ms 0 KB -