oj.uz

Submission #624976

# Submission time Handle Problem Language Result Execution time Memory
624976 2022-08-09T08:30:48 Z Mohammed_Atalah Wall (IOI14_wall) C++17
24 / 100
 1320 ms 78580 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  int o = k;
  vector<vector<int>> v;
  int e = 0;
  for (int i = 0; i < k ; i++) {
    if (op[i] == 2) {
      o = i;
      break;
    }
    e += 2;
    v.push_back({left[i], height[i], 1});
    v.push_back({right[i] + 1, height[i], -1});
  }
  sort(v.begin(), v.end());

  set<int> s;
  map<int, int> mp;
  vector<int> v1(n);
  for (int i = 0; i < e; i++) {
    if (v[i][0] >= n) {
      break;
    }
    if (v[i][2] == -1) {
      mp[v[i][1]]--;
      if (mp[v[i][1]] == 0) {
        s.erase(s.lower_bound(v[i][1]));
        if (s.size() == 0) {
          v1[v[i][0]] = -1;
        } else {
          auto it = s.end();
          it--;
          v1[v[i][0]] = *it;
        }
      }
    } else {
      mp[v[i][1]]++;
      if (mp[v[i][1]] == 1) {
        s.insert(v[i][1]);
      }
      auto it = s.end();
      it--;
      v1[v[i][0]] = *it;
    }
  }

  for (int i = 1; i < n; i++) {
    if (v1[i] == 0) {
      v1[i] = v1[i - 1];
    } else if (v1[i] == -1) {
      v1[i] = 0;
    }
  }


  vector<vector<int>> vv;
  e = 0;
  for (int i = o; i < k ; i++) {
    e += 2;
    vv.push_back({left[i], height[i], 1});
    vv.push_back({right[i] + 1, height[i], -1});
  }
  sort(vv.begin(), vv.end());

  set<int> ss;
  map<int, int> mpp;
  vector<int> v2(n);
  v2[0] = -1;
  for (int i = 0; i < e; i++) {
    if (vv[i][0] >= n) {
      break;
    }
    if (vv[i][2] == -1) {
      mpp[vv[i][1]]--;
      if (mpp[vv[i][1]] == 0) {
        ss.erase(ss.lower_bound(vv[i][1]));
        if (ss.size() == 0) {
          v2[vv[i][0]] = -1;
        } else {
          int w = *ss.begin();
          v2[vv[i][0]] = ((w == 0) ? -2 : w);
        }
      }
    } else {
      mpp[vv[i][1]]++;
      if (mpp[vv[i][1]] == 1) {
        ss.insert(vv[i][1]);
      }
      int w = *ss.begin();
      v2[vv[i][0]] = ((w == 0) ? -2 : w);
    }
  }
  // for (int i = 0; i < n; i++) {
  //   cout << v2[i] << " ";
  // } cout << endl;
  for (int i = 1; i < n; i++) {
    if (v2[i] == 0) {
      v2[i] = v2[i - 1];
    }
  }


  for (int i = 0; i < n; i++) {
    if (v2[i] == -2) {
      finalHeight[i] = 0;
    } else if (v2[i] != -1) {
      finalHeight[i] = min(v1[i], v2[i]);
    }  else {
      finalHeight[i] = v1[i];
    }
  }


  return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 6 ms 1324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 822 ms 78580 KB Output is correct
3 Correct 577 ms 33172 KB Output is correct
4 Correct 1320 ms 75996 KB Output is correct
5 Correct 386 ms 74464 KB Output is correct
6 Correct 379 ms 75604 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 5 ms 1296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 6 ms 1296 KB Output isn't correct
3 Halted 0 ms 0 KB -