oj.uz

Submission #905750

# Submission time Handle Problem Language Result Execution time Memory
905750 2024-01-13T04:35:57 Z nguyentunglam New Home (APIO18_new_home) C++17
47 / 100
 5000 ms 320720 KB 
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 3e5 + 10;

int n, k, q;

int x[N * 3], t[N], a[N], b[N], cost[N], c[N], y[N], ans[N];

int pre[N * 3], nxt[N * 3];

vector<int> rrh, open[N], close[N], event[N];

set<pair<int, int> > s[N];

bool alive[N * 3];

bool bug;

struct IT {
  int type;
  priority_queue<pair<int, int> > T[N << 2];
  void up(int s, int l, int r, int from, int to, pair<int, int> tmp) {
    if (l > to || r < from) return;
    if (from <= l && r <= to) {
      T[s].push(tmp);
      return;
    }
    int mid = l + r >> 1;
    up(s << 1, l, mid, from, to, tmp);
    up(s << 1 | 1, mid + 1, r, from, to, tmp);
  }

  int get(int s, int l, int r, int pos, int _pos) {
    int ret = 0;
    while (!T[s].empty()) {
      int i = T[s].top().second;
      int j = type ? pre[i] : nxt[i];
//      cout << abs(x[i] - _pos) << " " << abs(x[j] - _pos) << endl;
      if (alive[i] == 0 || abs(x[i] - _pos) > abs(x[j] - _pos)) T[s].pop();
      else if (x[i] == x[j]) T[s].pop();
      else {
//        cout << i << " " << j << " " << type << " " << pre[4] << " " << alive[i] << endl;
        ret = max(ret, abs(x[i] - _pos));
//        if (type) cout << x[i] << " " << i << " " << abs(x[i] - _pos) << " " << j << endl;
        break;
      }
    }
//    if (bug) {
//      if (!T[s].empty()) cout << T[s].top().second << endl;
//    }
    if (l == r) return ret;
    int mid = l + r >> 1;
    if (pos <= mid) return max(ret, get(s << 1, l, mid, pos, _pos));
    return max(ret, get(s << 1 | 1, mid + 1, r, pos, _pos));
  }
} it[2];

void compress () {
  sort(all(rrh));
  rrh.resize(unique(all(rrh)) - rrh.begin());
}

int id (int x) {
  return upper_bound(all(rrh), x) - rrh.begin();
}

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  it[0].type = 0;
  it[1].type = 1;

  cin >> n >> k >> q;

  for(int i = 1; i <= n; i++) cin >> x[i] >> t[i] >> a[i] >> b[i];

  for(int i = 1; i <= q; i++) cin >> c[i] >> y[i];

  for(int i = 1; i <= n; i++) {
    rrh.push_back(a[i]);
    rrh.push_back(b[i]);
  }
  for(int i = 1; i <= q; i++) rrh.push_back(y[i]);

  compress();

  for(int i = 1; i <= n; i++) {
    a[i] = id(a[i]);
    b[i] = id(b[i]);
    open[a[i]].push_back(i);
    close[b[i]].push_back(i);
  }

  for(int i = 1; i <= q; i++) {
    y[i] = id(y[i]);
    event[y[i]].push_back(i);
  }

  int m = rrh.size();

  rrh.clear();
  for(int i = 1; i <= q; i++) rrh.push_back(c[i]);
  compress();

  int cnt = n;
  int sz = rrh.size();

  for(int i = 1; i <= k; i++) {
    x[cnt + 1] = -1e9;
    x[cnt + 2] = 1e9;
    alive[cnt + 1] = alive[cnt + 2] = 1;
    s[i].insert({x[cnt + 1], cnt + 1});
    s[i].insert({x[cnt + 2], cnt + 2});
    it[1].up(1, 1, sz, 1, sz, make_pair(x[cnt + 2], cnt + 2));
    nxt[cnt + 1] = cnt + 2;
    pre[cnt + 2] = cnt + 1;
    cnt += 2;
  }


  for(int cur = 1; cur <= m; cur++) {
    for(int &j : open[cur]) {
      auto iter = s[t[j]].lower_bound(make_pair(x[j], j));
      int to = iter -> second;
      --iter;
      int from = iter -> second;
      int L = id(x[from] - 1) + 1, R = id(x[to]), pos = id(x[j]);
      int middle;
      middle = id(x[from] + x[j] >> 1);

//      if (j == 1) cout << from << " " << to << endl;

      it[0].up(1, 1, sz, L, middle, make_pair(-x[from], from));
      it[1].up(1, 1, sz, middle + 1, pos, make_pair(x[j], j));

      middle = id(x[j] + x[to] >> 1);
      pos = id(x[j] - 1) + 1;

      it[0].up(1, 1, sz, pos, middle, make_pair(-x[j], j));
      it[1].up(1, 1, sz, middle + 1, R, make_pair(x[to], to));

//      cout << pos << " " << middle << endl;


      nxt[from] = j;
      pre[j] = from;
      nxt[j] = to;
      pre[to] = j;
      s[t[j]].insert({x[j], j});
      alive[j] = 1;
    }
    for(int &j : event[cur]) {
      int cost1 = it[0].get(1, 1, sz, id(c[j]), c[j]);
      int cost2 = it[1].get(1, 1, sz, id(c[j]), c[j]);
//      cout << cost1 << " " << cost2 << endl;
      ans[j] = max(cost1, cost2);
    }
    for(int &j : close[cur]) {
      auto iter = s[t[j]].find(make_pair(x[j], j));
      ++iter;
      int to = iter -> second;
      --iter; --iter;
      int from = iter -> second;

      int L = id(x[from] - 1) + 1, R = id(x[to]), middle = id(x[from] + x[to] >> 1);

      it[0].up(1, 1, sz, L, middle, make_pair(-x[from], from));
      it[1].up(1, 1, sz, middle + 1, R, make_pair(x[to], to));
//      cout << from << " " << to << endl;
//      cout << L << " " << middle << " " << x[from] << endl;
//      cout << middle + 1 << " " << R << " " << x[to] << endl;
      nxt[from] = to;
      pre[to] = from;
      s[t[j]].erase(s[t[j]].find(make_pair(x[j], j)));
      alive[j] = 0;
    }
  }

//  cout << pre[1] << " " << nxt[1] << endl;

  bug = 1;
//  cout << it[1].T[1].size() << endl;
//  cout << it[1].get(1, 1, sz, id(c[3]), c[3]) << endl;

//  for(int i = nxt[n + 1]; i != n + 2; i = nxt[i]) cout << i << " "; cout << endl;

  for(int i = 1; i <= q; i++) {
    if (ans[i] > 1e8) ans[i] = -1;
    cout << ans[i] << endl;
  }
}

Compilation message

new_home.cpp: In member function 'void IT::up(int, int, int, int, int, std::pair<int, int>)':
new_home.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In member function 'int IT::get(int, int, int, int, int)':
new_home.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In function 'int32_t main()':
new_home.cpp:144:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  144 |       middle = id(x[from] + x[j] >> 1);
      |                   ~~~~~~~~^~~~~~
new_home.cpp:151:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  151 |       middle = id(x[j] + x[to] >> 1);
      |                   ~~~~~^~~~~~~
new_home.cpp:180:71: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  180 |       int L = id(x[from] - 1) + 1, R = id(x[to]), middle = id(x[from] + x[to] >> 1);
      |                                                               ~~~~~~~~^~~~~~~
new_home.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:81:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:82:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 125784 KB Output is correct
2 Correct 36 ms 125776 KB Output is correct
3 Correct 37 ms 125520 KB Output is correct
4 Correct 36 ms 125780 KB Output is correct
5 Correct 37 ms 125692 KB Output is correct
6 Correct 42 ms 125928 KB Output is correct
7 Correct 40 ms 125784 KB Output is correct
8 Correct 42 ms 125900 KB Output is correct
9 Correct 38 ms 125780 KB Output is correct
10 Correct 41 ms 125896 KB Output is correct
11 Correct 39 ms 125864 KB Output is correct
12 Correct 38 ms 125896 KB Output is correct
13 Correct 37 ms 125776 KB Output is correct
14 Correct 38 ms 125684 KB Output is correct
15 Correct 37 ms 125780 KB Output is correct
16 Correct 39 ms 125780 KB Output is correct
17 Correct 38 ms 125884 KB Output is correct
18 Correct 38 ms 125928 KB Output is correct
19 Correct 38 ms 125956 KB Output is correct
20 Correct 37 ms 125776 KB Output is correct
21 Correct 35 ms 125788 KB Output is correct
22 Correct 37 ms 125728 KB Output is correct
23 Correct 39 ms 125788 KB Output is correct
24 Correct 37 ms 125776 KB Output is correct
25 Correct 37 ms 125924 KB Output is correct
26 Correct 41 ms 125784 KB Output is correct
27 Correct 37 ms 125656 KB Output is correct
28 Correct 40 ms 125856 KB Output is correct
29 Correct 41 ms 125848 KB Output is correct
30 Correct 37 ms 125784 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 125784 KB Output is correct
2 Correct 36 ms 125776 KB Output is correct
3 Correct 37 ms 125520 KB Output is correct
4 Correct 36 ms 125780 KB Output is correct
5 Correct 37 ms 125692 KB Output is correct
6 Correct 42 ms 125928 KB Output is correct
7 Correct 40 ms 125784 KB Output is correct
8 Correct 42 ms 125900 KB Output is correct
9 Correct 38 ms 125780 KB Output is correct
10 Correct 41 ms 125896 KB Output is correct
11 Correct 39 ms 125864 KB Output is correct
12 Correct 38 ms 125896 KB Output is correct
13 Correct 37 ms 125776 KB Output is correct
14 Correct 38 ms 125684 KB Output is correct
15 Correct 37 ms 125780 KB Output is correct
16 Correct 39 ms 125780 KB Output is correct
17 Correct 38 ms 125884 KB Output is correct
18 Correct 38 ms 125928 KB Output is correct
19 Correct 38 ms 125956 KB Output is correct
20 Correct 37 ms 125776 KB Output is correct
21 Correct 35 ms 125788 KB Output is correct
22 Correct 37 ms 125728 KB Output is correct
23 Correct 39 ms 125788 KB Output is correct
24 Correct 37 ms 125776 KB Output is correct
25 Correct 37 ms 125924 KB Output is correct
26 Correct 41 ms 125784 KB Output is correct
27 Correct 37 ms 125656 KB Output is correct
28 Correct 40 ms 125856 KB Output is correct
29 Correct 41 ms 125848 KB Output is correct
30 Correct 37 ms 125784 KB Output is correct
31 Correct 1126 ms 168820 KB Output is correct
32 Correct 122 ms 131532 KB Output is correct
33 Correct 976 ms 152660 KB Output is correct
34 Correct 1225 ms 169664 KB Output is correct
35 Correct 1253 ms 164132 KB Output is correct
36 Correct 973 ms 151932 KB Output is correct
37 Correct 551 ms 154016 KB Output is correct
38 Correct 571 ms 146872 KB Output is correct
39 Correct 422 ms 148524 KB Output is correct
40 Correct 399 ms 146532 KB Output is correct
41 Correct 806 ms 149996 KB Output is correct
42 Correct 822 ms 151264 KB Output is correct
43 Correct 77 ms 132928 KB Output is correct
44 Correct 760 ms 149524 KB Output is correct
45 Correct 637 ms 146288 KB Output is correct
46 Correct 638 ms 145188 KB Output is correct
47 Correct 290 ms 147608 KB Output is correct
48 Correct 298 ms 147392 KB Output is correct
49 Correct 369 ms 148808 KB Output is correct
50 Correct 443 ms 154204 KB Output is correct
51 Correct 385 ms 146748 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 506 ms 278888 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 125784 KB Output is correct
2 Correct 36 ms 125776 KB Output is correct
3 Correct 37 ms 125520 KB Output is correct
4 Correct 36 ms 125780 KB Output is correct
5 Correct 37 ms 125692 KB Output is correct
6 Correct 42 ms 125928 KB Output is correct
7 Correct 40 ms 125784 KB Output is correct
8 Correct 42 ms 125900 KB Output is correct
9 Correct 38 ms 125780 KB Output is correct
10 Correct 41 ms 125896 KB Output is correct
11 Correct 39 ms 125864 KB Output is correct
12 Correct 38 ms 125896 KB Output is correct
13 Correct 37 ms 125776 KB Output is correct
14 Correct 38 ms 125684 KB Output is correct
15 Correct 37 ms 125780 KB Output is correct
16 Correct 39 ms 125780 KB Output is correct
17 Correct 38 ms 125884 KB Output is correct
18 Correct 38 ms 125928 KB Output is correct
19 Correct 38 ms 125956 KB Output is correct
20 Correct 37 ms 125776 KB Output is correct
21 Correct 35 ms 125788 KB Output is correct
22 Correct 37 ms 125728 KB Output is correct
23 Correct 39 ms 125788 KB Output is correct
24 Correct 37 ms 125776 KB Output is correct
25 Correct 37 ms 125924 KB Output is correct
26 Correct 41 ms 125784 KB Output is correct
27 Correct 37 ms 125656 KB Output is correct
28 Correct 40 ms 125856 KB Output is correct
29 Correct 41 ms 125848 KB Output is correct
30 Correct 37 ms 125784 KB Output is correct
31 Correct 1126 ms 168820 KB Output is correct
32 Correct 122 ms 131532 KB Output is correct
33 Correct 976 ms 152660 KB Output is correct
34 Correct 1225 ms 169664 KB Output is correct
35 Correct 1253 ms 164132 KB Output is correct
36 Correct 973 ms 151932 KB Output is correct
37 Correct 551 ms 154016 KB Output is correct
38 Correct 571 ms 146872 KB Output is correct
39 Correct 422 ms 148524 KB Output is correct
40 Correct 399 ms 146532 KB Output is correct
41 Correct 806 ms 149996 KB Output is correct
42 Correct 822 ms 151264 KB Output is correct
43 Correct 77 ms 132928 KB Output is correct
44 Correct 760 ms 149524 KB Output is correct
45 Correct 637 ms 146288 KB Output is correct
46 Correct 638 ms 145188 KB Output is correct
47 Correct 290 ms 147608 KB Output is correct
48 Correct 298 ms 147392 KB Output is correct
49 Correct 369 ms 148808 KB Output is correct
50 Correct 443 ms 154204 KB Output is correct
51 Correct 385 ms 146748 KB Output is correct
52 Correct 566 ms 157484 KB Output is correct
53 Correct 603 ms 154844 KB Output is correct
54 Correct 1035 ms 167728 KB Output is correct
55 Correct 700 ms 157220 KB Output is correct
56 Correct 599 ms 156900 KB Output is correct
57 Correct 812 ms 153588 KB Output is correct
58 Correct 770 ms 157200 KB Output is correct
59 Correct 688 ms 157236 KB Output is correct
60 Correct 799 ms 154348 KB Output is correct
61 Correct 93 ms 141640 KB Output is correct
62 Correct 629 ms 156972 KB Output is correct
63 Correct 816 ms 163044 KB Output is correct
64 Correct 783 ms 164940 KB Output is correct
65 Correct 1104 ms 163424 KB Output is correct
66 Correct 896 ms 153548 KB Output is correct
67 Correct 206 ms 137852 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 125784 KB Output is correct
2 Correct 36 ms 125776 KB Output is correct
3 Correct 37 ms 125520 KB Output is correct
4 Correct 36 ms 125780 KB Output is correct
5 Correct 37 ms 125692 KB Output is correct
6 Correct 42 ms 125928 KB Output is correct
7 Correct 40 ms 125784 KB Output is correct
8 Correct 42 ms 125900 KB Output is correct
9 Correct 38 ms 125780 KB Output is correct
10 Correct 41 ms 125896 KB Output is correct
11 Correct 39 ms 125864 KB Output is correct
12 Correct 38 ms 125896 KB Output is correct
13 Correct 37 ms 125776 KB Output is correct
14 Correct 38 ms 125684 KB Output is correct
15 Correct 37 ms 125780 KB Output is correct
16 Correct 39 ms 125780 KB Output is correct
17 Correct 38 ms 125884 KB Output is correct
18 Correct 38 ms 125928 KB Output is correct
19 Correct 38 ms 125956 KB Output is correct
20 Correct 37 ms 125776 KB Output is correct
21 Correct 35 ms 125788 KB Output is correct
22 Correct 37 ms 125728 KB Output is correct
23 Correct 39 ms 125788 KB Output is correct
24 Correct 37 ms 125776 KB Output is correct
25 Correct 37 ms 125924 KB Output is correct
26 Correct 41 ms 125784 KB Output is correct
27 Correct 37 ms 125656 KB Output is correct
28 Correct 40 ms 125856 KB Output is correct
29 Correct 41 ms 125848 KB Output is correct
30 Correct 37 ms 125784 KB Output is correct
31 Correct 1126 ms 168820 KB Output is correct
32 Correct 122 ms 131532 KB Output is correct
33 Correct 976 ms 152660 KB Output is correct
34 Correct 1225 ms 169664 KB Output is correct
35 Correct 1253 ms 164132 KB Output is correct
36 Correct 973 ms 151932 KB Output is correct
37 Correct 551 ms 154016 KB Output is correct
38 Correct 571 ms 146872 KB Output is correct
39 Correct 422 ms 148524 KB Output is correct
40 Correct 399 ms 146532 KB Output is correct
41 Correct 806 ms 149996 KB Output is correct
42 Correct 822 ms 151264 KB Output is correct
43 Correct 77 ms 132928 KB Output is correct
44 Correct 760 ms 149524 KB Output is correct
45 Correct 637 ms 146288 KB Output is correct
46 Correct 638 ms 145188 KB Output is correct
47 Correct 290 ms 147608 KB Output is correct
48 Correct 298 ms 147392 KB Output is correct
49 Correct 369 ms 148808 KB Output is correct
50 Correct 443 ms 154204 KB Output is correct
51 Correct 385 ms 146748 KB Output is correct
52 Execution timed out 5089 ms 320720 KB Time limit exceeded
53 Halted 0 ms 0 KB -