oj.uz

Submission #905757

# Submission time Handle Problem Language Result Execution time Memory
905757 2024-01-13T04:38:30 Z nguyentunglam New Home (APIO18_new_home) C++17
47 / 100
 5000 ms 373796 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 * 3], close[N * 3], event[N * 3];

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;
    }
  }

  cerr << 1.0 * clock() / CLOCKS_PER_SEC << 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:143:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  143 |       middle = id(x[from] + x[j] >> 1);
      |                   ~~~~~~~~^~~~~~
new_home.cpp:150:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  150 |       middle = id(x[j] + x[to] >> 1);
      |                   ~~~~~^~~~~~~
new_home.cpp:179:71: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  179 |       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 50 ms 166736 KB Output is correct
2 Correct 50 ms 166660 KB Output is correct
3 Correct 53 ms 166744 KB Output is correct
4 Correct 51 ms 166820 KB Output is correct
5 Correct 52 ms 166696 KB Output is correct
6 Correct 54 ms 166744 KB Output is correct
7 Correct 53 ms 166896 KB Output is correct
8 Correct 55 ms 166932 KB Output is correct
9 Correct 51 ms 166968 KB Output is correct
10 Correct 50 ms 166736 KB Output is correct
11 Correct 51 ms 166916 KB Output is correct
12 Correct 52 ms 166740 KB Output is correct
13 Correct 50 ms 166664 KB Output is correct
14 Correct 51 ms 166992 KB Output is correct
15 Correct 49 ms 166960 KB Output is correct
16 Correct 56 ms 166940 KB Output is correct
17 Correct 51 ms 166992 KB Output is correct
18 Correct 54 ms 166724 KB Output is correct
19 Correct 50 ms 166892 KB Output is correct
20 Correct 59 ms 166760 KB Output is correct
21 Correct 47 ms 166868 KB Output is correct
22 Correct 51 ms 166744 KB Output is correct
23 Correct 53 ms 166880 KB Output is correct
24 Correct 50 ms 166976 KB Output is correct
25 Correct 52 ms 166896 KB Output is correct
26 Correct 56 ms 166764 KB Output is correct
27 Correct 50 ms 166888 KB Output is correct
28 Correct 53 ms 166756 KB Output is correct
29 Correct 53 ms 166744 KB Output is correct
30 Correct 52 ms 166740 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 166736 KB Output is correct
2 Correct 50 ms 166660 KB Output is correct
3 Correct 53 ms 166744 KB Output is correct
4 Correct 51 ms 166820 KB Output is correct
5 Correct 52 ms 166696 KB Output is correct
6 Correct 54 ms 166744 KB Output is correct
7 Correct 53 ms 166896 KB Output is correct
8 Correct 55 ms 166932 KB Output is correct
9 Correct 51 ms 166968 KB Output is correct
10 Correct 50 ms 166736 KB Output is correct
11 Correct 51 ms 166916 KB Output is correct
12 Correct 52 ms 166740 KB Output is correct
13 Correct 50 ms 166664 KB Output is correct
14 Correct 51 ms 166992 KB Output is correct
15 Correct 49 ms 166960 KB Output is correct
16 Correct 56 ms 166940 KB Output is correct
17 Correct 51 ms 166992 KB Output is correct
18 Correct 54 ms 166724 KB Output is correct
19 Correct 50 ms 166892 KB Output is correct
20 Correct 59 ms 166760 KB Output is correct
21 Correct 47 ms 166868 KB Output is correct
22 Correct 51 ms 166744 KB Output is correct
23 Correct 53 ms 166880 KB Output is correct
24 Correct 50 ms 166976 KB Output is correct
25 Correct 52 ms 166896 KB Output is correct
26 Correct 56 ms 166764 KB Output is correct
27 Correct 50 ms 166888 KB Output is correct
28 Correct 53 ms 166756 KB Output is correct
29 Correct 53 ms 166744 KB Output is correct
30 Correct 52 ms 166740 KB Output is correct
31 Correct 1433 ms 207768 KB Output is correct
32 Correct 130 ms 171500 KB Output is correct
33 Correct 1020 ms 190740 KB Output is correct
34 Correct 1264 ms 207956 KB Output is correct
35 Correct 1202 ms 202444 KB Output is correct
36 Correct 914 ms 190180 KB Output is correct
37 Correct 578 ms 192360 KB Output is correct
38 Correct 488 ms 185036 KB Output is correct
39 Correct 394 ms 186468 KB Output is correct
40 Correct 375 ms 184748 KB Output is correct
41 Correct 777 ms 188084 KB Output is correct
42 Correct 805 ms 189376 KB Output is correct
43 Correct 95 ms 171468 KB Output is correct
44 Correct 898 ms 187716 KB Output is correct
45 Correct 707 ms 184320 KB Output is correct
46 Correct 688 ms 183176 KB Output is correct
47 Correct 338 ms 186036 KB Output is correct
48 Correct 321 ms 185620 KB Output is correct
49 Correct 381 ms 186976 KB Output is correct
50 Correct 467 ms 192496 KB Output is correct
51 Correct 400 ms 185036 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 166736 KB Output is correct
2 Correct 50 ms 166660 KB Output is correct
3 Correct 53 ms 166744 KB Output is correct
4 Correct 51 ms 166820 KB Output is correct
5 Correct 52 ms 166696 KB Output is correct
6 Correct 54 ms 166744 KB Output is correct
7 Correct 53 ms 166896 KB Output is correct
8 Correct 55 ms 166932 KB Output is correct
9 Correct 51 ms 166968 KB Output is correct
10 Correct 50 ms 166736 KB Output is correct
11 Correct 51 ms 166916 KB Output is correct
12 Correct 52 ms 166740 KB Output is correct
13 Correct 50 ms 166664 KB Output is correct
14 Correct 51 ms 166992 KB Output is correct
15 Correct 49 ms 166960 KB Output is correct
16 Correct 56 ms 166940 KB Output is correct
17 Correct 51 ms 166992 KB Output is correct
18 Correct 54 ms 166724 KB Output is correct
19 Correct 50 ms 166892 KB Output is correct
20 Correct 59 ms 166760 KB Output is correct
21 Correct 47 ms 166868 KB Output is correct
22 Correct 51 ms 166744 KB Output is correct
23 Correct 53 ms 166880 KB Output is correct
24 Correct 50 ms 166976 KB Output is correct
25 Correct 52 ms 166896 KB Output is correct
26 Correct 56 ms 166764 KB Output is correct
27 Correct 50 ms 166888 KB Output is correct
28 Correct 53 ms 166756 KB Output is correct
29 Correct 53 ms 166744 KB Output is correct
30 Correct 52 ms 166740 KB Output is correct
31 Correct 1433 ms 207768 KB Output is correct
32 Correct 130 ms 171500 KB Output is correct
33 Correct 1020 ms 190740 KB Output is correct
34 Correct 1264 ms 207956 KB Output is correct
35 Correct 1202 ms 202444 KB Output is correct
36 Correct 914 ms 190180 KB Output is correct
37 Correct 578 ms 192360 KB Output is correct
38 Correct 488 ms 185036 KB Output is correct
39 Correct 394 ms 186468 KB Output is correct
40 Correct 375 ms 184748 KB Output is correct
41 Correct 777 ms 188084 KB Output is correct
42 Correct 805 ms 189376 KB Output is correct
43 Correct 95 ms 171468 KB Output is correct
44 Correct 898 ms 187716 KB Output is correct
45 Correct 707 ms 184320 KB Output is correct
46 Correct 688 ms 183176 KB Output is correct
47 Correct 338 ms 186036 KB Output is correct
48 Correct 321 ms 185620 KB Output is correct
49 Correct 381 ms 186976 KB Output is correct
50 Correct 467 ms 192496 KB Output is correct
51 Correct 400 ms 185036 KB Output is correct
52 Correct 684 ms 195428 KB Output is correct
53 Correct 637 ms 192464 KB Output is correct
54 Correct 1057 ms 204076 KB Output is correct
55 Correct 753 ms 192712 KB Output is correct
56 Correct 643 ms 193068 KB Output is correct
57 Correct 817 ms 191404 KB Output is correct
58 Correct 765 ms 193096 KB Output is correct
59 Correct 742 ms 193184 KB Output is correct
60 Correct 799 ms 191944 KB Output is correct
61 Correct 110 ms 180140 KB Output is correct
62 Correct 606 ms 194752 KB Output is correct
63 Correct 794 ms 198836 KB Output is correct
64 Correct 824 ms 200832 KB Output is correct
65 Correct 1208 ms 201164 KB Output is correct
66 Correct 826 ms 191916 KB Output is correct
67 Correct 187 ms 177564 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 166736 KB Output is correct
2 Correct 50 ms 166660 KB Output is correct
3 Correct 53 ms 166744 KB Output is correct
4 Correct 51 ms 166820 KB Output is correct
5 Correct 52 ms 166696 KB Output is correct
6 Correct 54 ms 166744 KB Output is correct
7 Correct 53 ms 166896 KB Output is correct
8 Correct 55 ms 166932 KB Output is correct
9 Correct 51 ms 166968 KB Output is correct
10 Correct 50 ms 166736 KB Output is correct
11 Correct 51 ms 166916 KB Output is correct
12 Correct 52 ms 166740 KB Output is correct
13 Correct 50 ms 166664 KB Output is correct
14 Correct 51 ms 166992 KB Output is correct
15 Correct 49 ms 166960 KB Output is correct
16 Correct 56 ms 166940 KB Output is correct
17 Correct 51 ms 166992 KB Output is correct
18 Correct 54 ms 166724 KB Output is correct
19 Correct 50 ms 166892 KB Output is correct
20 Correct 59 ms 166760 KB Output is correct
21 Correct 47 ms 166868 KB Output is correct
22 Correct 51 ms 166744 KB Output is correct
23 Correct 53 ms 166880 KB Output is correct
24 Correct 50 ms 166976 KB Output is correct
25 Correct 52 ms 166896 KB Output is correct
26 Correct 56 ms 166764 KB Output is correct
27 Correct 50 ms 166888 KB Output is correct
28 Correct 53 ms 166756 KB Output is correct
29 Correct 53 ms 166744 KB Output is correct
30 Correct 52 ms 166740 KB Output is correct
31 Correct 1433 ms 207768 KB Output is correct
32 Correct 130 ms 171500 KB Output is correct
33 Correct 1020 ms 190740 KB Output is correct
34 Correct 1264 ms 207956 KB Output is correct
35 Correct 1202 ms 202444 KB Output is correct
36 Correct 914 ms 190180 KB Output is correct
37 Correct 578 ms 192360 KB Output is correct
38 Correct 488 ms 185036 KB Output is correct
39 Correct 394 ms 186468 KB Output is correct
40 Correct 375 ms 184748 KB Output is correct
41 Correct 777 ms 188084 KB Output is correct
42 Correct 805 ms 189376 KB Output is correct
43 Correct 95 ms 171468 KB Output is correct
44 Correct 898 ms 187716 KB Output is correct
45 Correct 707 ms 184320 KB Output is correct
46 Correct 688 ms 183176 KB Output is correct
47 Correct 338 ms 186036 KB Output is correct
48 Correct 321 ms 185620 KB Output is correct
49 Correct 381 ms 186976 KB Output is correct
50 Correct 467 ms 192496 KB Output is correct
51 Correct 400 ms 185036 KB Output is correct
52 Execution timed out 5034 ms 347952 KB Time limit exceeded
53 Halted 0 ms 0 KB -