oj.uz

Submission #986792

# Submission time Handle Problem Language Result Execution time Memory
986792 2024-05-21T08:41:28 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 642 ms 70236 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())

typedef long long ll;
typedef pair<int, int> point;

const int off = 1 << 19, inf = 1e9;

point T[2 * off];

point Merge(point A, point B) {
  point ret = A;
  ret.first = min(ret.first, B.second);
  ret.first = max(ret.first, B.first);
  ret.second = min(A.second, B.second);

  return ret;
}

void upd(int x, point v) {
  x += off;
  T[x] = v;
  for(x /= 2; x; x /= 2) {
    T[x] = Merge(T[x * 2], T[x * 2 + 1]);
  }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  vector<pair<point, int>> e;
  REP(i, k) {
    e.push_back({{left[i], 0}, i});
    e.push_back({{right[i], 2}, i});
  }
  REP(i, n) {
    e.push_back({{i, 1}, i});
  }

  REP(i, 2 * off) T[i] = {0, inf};

  sort(e.begin(), e.end());

  for(auto p: e) {
    if(p.first.second == 0) {
      point v = {0, inf};
      int i = p.second;
      if(op[i] == 1) {
        v.first = height[i];
      }
      else {
        v.second = height[i];
      }
      upd(i, v);
    }
    else if(p.first.second == 1) {
      finalHeight[p.second] = T[1].first;
    }
    else {
      upd(p.second, {0, inf});
    }
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 7 ms 8988 KB Output is correct
3 Correct 4 ms 8796 KB Output is correct
4 Correct 10 ms 9188 KB Output is correct
5 Correct 8 ms 9048 KB Output is correct
6 Correct 10 ms 9052 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8536 KB Output is correct
2 Correct 250 ms 33952 KB Output is correct
3 Correct 152 ms 19604 KB Output is correct
4 Correct 402 ms 42660 KB Output is correct
5 Correct 324 ms 43196 KB Output is correct
6 Correct 313 ms 41400 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8536 KB Output is correct
2 Correct 6 ms 8984 KB Output is correct
3 Correct 5 ms 8792 KB Output is correct
4 Correct 8 ms 9052 KB Output is correct
5 Correct 8 ms 9052 KB Output is correct
6 Correct 8 ms 9052 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct
8 Correct 252 ms 33980 KB Output is correct
9 Correct 143 ms 21024 KB Output is correct
10 Correct 403 ms 42416 KB Output is correct
11 Correct 316 ms 43192 KB Output is correct
12 Correct 308 ms 41404 KB Output is correct
13 Correct 3 ms 8536 KB Output is correct
14 Correct 260 ms 34320 KB Output is correct
15 Correct 26 ms 10760 KB Output is correct
16 Correct 385 ms 42536 KB Output is correct
17 Correct 309 ms 41908 KB Output is correct
18 Correct 313 ms 41912 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 7 ms 8988 KB Output is correct
3 Correct 5 ms 8796 KB Output is correct
4 Correct 8 ms 9000 KB Output is correct
5 Correct 8 ms 9052 KB Output is correct
6 Correct 8 ms 9156 KB Output is correct
7 Correct 4 ms 8540 KB Output is correct
8 Correct 259 ms 34164 KB Output is correct
9 Correct 139 ms 20948 KB Output is correct
10 Correct 377 ms 42664 KB Output is correct
11 Correct 312 ms 43196 KB Output is correct
12 Correct 308 ms 41560 KB Output is correct
13 Correct 4 ms 8636 KB Output is correct
14 Correct 248 ms 34164 KB Output is correct
15 Correct 26 ms 10704 KB Output is correct
16 Correct 401 ms 42552 KB Output is correct
17 Correct 307 ms 41912 KB Output is correct
18 Correct 310 ms 41912 KB Output is correct
19 Correct 642 ms 69948 KB Output is correct
20 Correct 597 ms 69964 KB Output is correct
21 Correct 600 ms 69892 KB Output is correct
22 Correct 606 ms 70020 KB Output is correct
23 Correct 589 ms 69980 KB Output is correct
24 Correct 625 ms 69956 KB Output is correct
25 Correct 622 ms 69976 KB Output is correct
26 Correct 617 ms 69984 KB Output is correct
27 Correct 616 ms 70236 KB Output is correct
28 Correct 622 ms 70092 KB Output is correct
29 Correct 601 ms 70064 KB Output is correct
30 Correct 600 ms 70116 KB Output is correct