제출 #788137

#제출 시각아이디문제언어결과실행 시간메모리
788137JoenPoenMan벽 (IOI14_wall)C++17
24 / 100
495 ms47464 KiB
#include <bits/stdc++.h> #define ALL(arr) begin(arr), end(arr) using namespace std; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { // x, ind, end, adding, height vector<tuple<int, int, bool, int>> addactions; vector<tuple<int, int, bool, int>> remactions; for (int i = 0; i < k; i++) { if (op[i] == 1) { addactions.push_back({left[i], i, false, height[i]}); addactions.push_back({right[i]+1, i, true, height[i]}); } else { remactions.push_back({left[i], i, false, height[i]}); remactions.push_back({right[i]+1, i, true, height[i]}); } } sort(ALL(addactions)); sort(ALL(remactions)); int px = 0; multiset<int, greater<int>> prevHeights; prevHeights.insert(0); for (auto [x, ind, end, goalheight] : addactions) { fill(finalHeight + px, finalHeight + x, *prevHeights.begin()); px = x; if (!end) { prevHeights.insert(goalheight); } else { auto it = prevHeights.find(goalheight); prevHeights.erase(it); } } fill(finalHeight + px, finalHeight + n, 0); px = 0; multiset<int> prevHeights2; prevHeights2.insert(1e8); int maxH = 0; for (auto [x, ind, end, goalheight] : remactions) { for (int i = px; i < x; i++) { maxH = finalHeight[i]; finalHeight[i] = min(*prevHeights2.begin(), maxH); } px = x; if (!end) { prevHeights2.insert(goalheight); } else { auto it = prevHeights2.find(goalheight); prevHeights2.erase(it); } } return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...