oj.uz

Submission #399738

# Submission time Handle Problem Language Result Execution time Memory
399738 2021-05-06T14:19:17 Z my99n New Home (APIO18_new_home) C++17
5 / 100
 5000 ms 8564 KB 
#include<bits/stdc++.h>
using namespace std;

struct event {
  int et, x, t, y, i;
  bool operator < (const event & o) const {
    if (y == o.y) return et < o.et; // open query close
    return y < o.y;
  }
};
vector<event> e;
set<pair<int,int>> s[500];
int ans[100100];

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k, q; cin >> n >> k >> q;
  assert(k < 500);
  for (int i = 1; i <= n; i++) {
    int x, t, a, b; cin >> x >> t >> a >> b;
    e.push_back({1, x, t, a, i});
    e.push_back({3, x, t, b, i});
  }
  for (int i = 1; i <= q; i++) {
    int l, y; cin >> l >> y;
    e.push_back({2, l, 0, y, i});
  }
  sort(e.begin(), e.end());
  for (auto [et, x, t, y, i] : e) {
    if (et == 1) s[t].insert({x, i});
    if (et == 3) s[t].erase({x, i});
    if (et == 2) {
      for (int type = 1; type <= k; type++) {
        if (s[type].empty()) {
          ans[i] = -1;
          break;
        }
        int mn = 1e9;
        for (auto [loc, ind] : s[type]) {
          mn = min(mn, abs(x - loc));
        }
        ans[i] = max(ans[i], mn);
      }
      // for (int type = 1; type <= k; type++) {
      //   if (s[type].empty()) {
      //     ans[i] = -1;
      //     break;
      //   }
      //   auto a = s[type].lower_bound({x, 1e9});
      //   auto b = a++;
      //   int mn = min(abs(x - a->first), abs(b->first-x));
      //   ans[i] = max(ans[i], mn);
      // }
    }
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << endl;
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 352 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 412 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 360 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 3 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 3 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 436 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 336 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 352 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 412 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 360 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 3 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 3 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 436 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 336 KB Output is correct
31 Execution timed out 5082 ms 8564 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 352 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 412 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 360 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 3 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 3 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 436 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 336 KB Output is correct
31 Execution timed out 5082 ms 8564 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 352 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 412 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 360 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 3 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 3 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 436 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 336 KB Output is correct
31 Execution timed out 5082 ms 8564 KB Time limit exceeded
32 Halted 0 ms 0 KB -