| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 387521 | peijar | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wall.h"#include <bits/stdc++.h>using namespace std; const int MAXN = 8e6+10;const int INF = 1e9; int segVal[MAXN], lazyMax[MAXN], lazyMin[MAXN];int iDeb[MAXN], iFin[MAXN]; void buildTree(int iNoeud, int li, int ri){ iDeb[iNoeud] = li, iFin[iNoeud] = ri; lazyMax[iNoeud] = 0; lazyMin[iNoeud] = INF; if (li == ri) return; buildTree(2*iNoeud, li, (li+ri)/2); buildTree(2*iNoeud+1, (li+ri)/2+1, ri);} void changeMax(int iNoeud, int val){ lazyMax[iNoeud] = max(lazyMax[iNoeud], val); lazyMin[iNoeud] = max(lazyMin[iNoeud], val);} void changeMin(int iNoeud, int val){ lazyMin[iNoeud] = min(lazyMin[iNoeud], val); lazyMax[iNoeud] = min(lazyMax[iNoeud], val);} void pushDown(int iNoeud){ segVal[iNoeud] = max(segVal[iNoeud], lazyMax[iNoeud]); segVal[iNoeud] = min(segVal[iNoeud], lazyMin[iNoeud]); if (iDeb[iNoeud] < iFin[iNoeud]) { changeMax(2*iNoeud, lazyMax[iNoeud]); changeMin(2*iNoeud, lazyMin[iNoeud]); changeMax(2*iNoeud+1, lazyMax[iNoeud]); changeMin(2*iNoeud+1, lazyMin[iNoeud]); } lazyMax[iNoeud] = 0, lazyMin[iNoeud] = INF;} int getVal(int iNoeud, int pos){ pushDown(iNoeud); if (iDeb[iNoeud] > pos or iFin[iNoeud] < pos) return 0; if (iDeb[iNoeud] == iFin[iNoeud]) return segVal[iNoeud]; return getVal(2*iNoeud, pos) + getVal(2*iNoeud+1, pos);} void update(int iNoeud, int deb, int fin, int op, int val){ pushDown(iNoeud); if (deb > iFin[iNoeud] or fin < iDeb[iNoeud]) return; if (deb <= iDeb[iNoeud] and iFin[iNoeud] <= fin) { if (op==1) lazyMax[iNoeud] = val; else lazyMin[iNoeud] = val; pushDown(iNoeud); return ; } update(2*iNoeud, deb, fin, op, val); update(2*iNoeud+1, deb, fin, op, val);} void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ buildTree(1, 0, n-1); for (int i(0); i < k; ++i) update(1, left[i], right[i], op[i], height[i]); for (int i(0); i < n; ++i) finalHeight[i] = getVal(1, i); return;}#include <bits/stdc++.h>using namespace std; const int MAXN = 48e6+10;const int INF = 1e9; int segVal[MAXN], lazyMax[MAXN], lazyMin[MAXN];int iDeb[MAXN], iFin[MAXN]; void buildTree(int iNoeud, int li, int ri){ iDeb[iNoeud] = li, iFin[iNoeud] = ri; lazyMax[iNoeud] = 0; lazyMin[iNoeud] = INF; if (li == ri) return; buildTree(2*iNoeud, li, (li+ri)/2); buildTree(2*iNoeud+1, (li+ri)/2+1, ri);} void changeMax(int iNoeud, int val){ lazyMax[iNoeud] = max(lazyMax[iNoeud], val); lazyMin[iNoeud] = max(lazyMin[iNoeud], val);} void changeMin(int iNoeud, int val){ lazyMin[iNoeud] = min(lazyMin[iNoeud], val); lazyMax[iNoeud] = min(lazyMax[iNoeud], val);} void pushDown(int iNoeud){ segVal[iNoeud] = max(segVal[iNoeud], lazyMax[iNoeud]); segVal[iNoeud] = min(segVal[iNoeud], lazyMin[iNoeud]); if (iDeb[iNoeud] < iFin[iNoeud]) { changeMax(2*iNoeud, lazyMax[iNoeud]); changeMin(2*iNoeud, lazyMin[iNoeud]); changeMax(2*iNoeud+1, lazyMax[iNoeud]); changeMin(2*iNoeud+1, lazyMin[iNoeud]); } lazyMax[iNoeud] = 0, lazyMin[iNoeud] = INF;} int getVal(int iNoeud, int pos){ pushDown(iNoeud); if (iDeb[iNoeud] > pos or iFin[iNoeud] < pos) return 0; if (iDeb[iNoeud] == iFin[iNoeud]) return segVal[iNoeud]; return getVal(2*iNoeud, pos) + getVal(2*iNoeud+1, pos);} void update(int iNoeud, int deb, int fin, int op, int val){ pushDown(iNoeud); if (deb > iFin[iNoeud] or fin < iDeb[iNoeud]) return; if (deb <= iDeb[iNoeud] and iFin[iNoeud] <= fin) { if (op==1) lazyMax[iNoeud] = val; else lazyMin[iNoeud] = val; pushDown(iNoeud); return ; } update(2*iNoeud, deb, fin, op, val); update(2*iNoeud+1, deb, fin, op, val);} void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ buildTree(1, 0, n-1); for (int i(0); i < k; ++i) update(1, left[i], right[i], op[i], height[i]); for (int i(0); i < n; ++i) finalHeight[i] = getVal(1, i); return;}#include <bits/stdc++.h>using namespace std; const int MAXN = 48e6+10;const int INF = 1e9; int segVal[MAXN], lazyMax[MAXN], lazyMin[MAXN];int iDeb[MAXN], iFin[MAXN]; void buildTree(int iNoeud, int li, int ri){ iDeb[iNoeud] = li, iFin[iNoeud] = ri; lazyMax[iNoeud] = 0; lazyMin[iNoeud] = INF; if (li == ri) return; buildTree(2*iNoeud, li, (li+ri)/2); buildTree(2*iNoeud+1, (li+ri)/2+1, ri);} void changeMax(int iNoeud, int val){ lazyMax[iNoeud] = max(lazyMax[iNoeud], val); lazyMin[iNoeud] = max(lazyMin[iNoeud], val);} void changeMin(int iNoeud, int val){ lazyMin[iNoeud] = min(lazyMin[iNoeud], val); lazyMax[iNoeud] = min(lazyMax[iNoeud], val);} void pushDown(int iNoeud){ segVal[iNoeud] = max(segVal[iNoeud], lazyMax[iNoeud]); segVal[iNoeud] = min(segVal[iNoeud], lazyMin[iNoeud]); if (iDeb[iNoeud] < iFin[iNoeud]) { changeMax(2*iNoeud, lazyMax[iNoeud]); changeMin(2*iNoeud, lazyMin[iNoeud]); changeMax(2*iNoeud+1, lazyMax[iNoeud]); changeMin(2*iNoeud+1, lazyMin[iNoeud]); } lazyMax[iNoeud] = 0, lazyMin[iNoeud] = INF;} int getVal(int iNoeud, int pos){ pushDown(iNoeud); if (iDeb[iNoeud] > pos or iFin[iNoeud] < pos) return 0; if (iDeb[iNoeud] == iFin[iNoeud]) return segVal[iNoeud]; return getVal(2*iNoeud, pos) + getVal(2*iNoeud+1, pos);} void update(int iNoeud, int deb, int fin, int op, int val){ pushDown(iNoeud); if (deb > iFin[iNoeud] or fin < iDeb[iNoeud]) return; if (deb <= iDeb[iNoeud] and iFin[iNoeud] <= fin) { if (op==1) lazyMax[iNoeud] = val; else lazyMin[iNoeud] = val; pushDown(iNoeud); return ; } update(2*iNoeud, deb, fin, op, val); update(2*iNoeud+1, deb, fin, op, val);} void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ buildTree(1, 0, n-1); for (int i(0); i < k; ++i) update(1, left[i], right[i], op[i], height[i]); for (int i(0); i < n; ++i) finalHeight[i] = getVal(1, i); return;}#include <bits/stdc++.h>using namespace std; const int MAXN = 4e6+10;const int INF = 1e9; int segVal[MAXN], lazyMax[MAXN], lazyMin[MAXN];int iDeb[MAXN], iFin[MAXN]; void buildTree(int iNoeud, int li, int ri){ iDeb[iNoeud] = li, iFin[iNoeud] = ri; lazyMax[iNoeud] = 0; lazyMin[iNoeud] = INF; if (li == ri) return; buildTree(2*iNoeud, li, (li+ri)/2); buildTree(2*iNoeud+1, (li+ri)/2+1, ri);} void changeMax(int iNoeud, int val){ lazyMax[iNoeud] = max(lazyMax[iNoeud], val); lazyMin[iNoeud] = max(lazyMin[iNoeud], val);} void changeMin(int iNoeud, int val){ lazyMin[iNoeud] = min(lazyMin[iNoeud], val); lazyMax[iNoeud] = min(lazyMax[iNoeud], val);} void pushDown(int iNoeud){ segVal[iNoeud] = max(segVal[iNoeud], lazyMax[iNoeud]); segVal[iNoeud] = min(segVal[iNoeud], lazyMin[iNoeud]); if (iDeb[iNoeud] < iFin[iNoeud]) { changeMax(2*iNoeud, lazyMax[iNoeud]); changeMin(2*iNoeud, lazyMin[iNoeud]); changeMax(2*iNoeud+1, lazyMax[iNoeud]); changeMin(2*iNoeud+1, lazyMin[iNoeud]); } lazyMax[iNoeud] = 0, lazyMin[iNoeud] = INF;} int getVal(int iNoeud, int pos){ pushDown(iNoeud); if (iDeb[iNoeud] > pos or iFin[iNoeud] < pos) return 0; if (iDeb[iNoeud] == iFin[iNoeud]) return segVal[iNoeud]; return getVal(2*iNoeud, pos) + getVal(2*iNoeud+1, pos);} void update(int iNoeud, int deb, int fin, int op, int val){ pushDown(iNoeud); if (deb > iFin[iNoeud] or fin < iDeb[iNoeud]) return; if (deb <= iDeb[iNoeud] and iFin[iNoeud] <= fin) { if (op==1) lazyMax[iNoeud] = val; else lazyMin[iNoeud] = val; pushDown(iNoeud); return ; } update(2*iNoeud, deb, fin, op, val); update(2*iNoeud+1, deb, fin, op, val);} void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ buildTree(1, 0, n-1); for (int i(0); i < k; ++i) update(1, left[i], right[i], op[i], height[i]); for (int i(0); i < n; ++i) finalHeight[i] = getVal(1, i); return;}#include <bits/stdc++.h>using namespace std; const int MAXN = 4e6+10;const int INF = 1e9; int segVal[MAXN], lazyMax[MAXN], lazyMin[MAXN];int iDeb[MAXN], iFin[MAXN]; void buildTree(int iNoeud, int li, int ri){ iDeb[iNoeud] = li, iFin[iNoeud] = ri; lazyMax[iNoeud] = 0; lazyMin[iNoeud] = INF; if (li == ri) return; buildTree(2*iNoeud, li, (li+ri)/2); buildTree(2*iNoeud+1, (li+ri)/2+1, ri);} void changeMax(int iNoeud, int val){ lazyMax[iNoeud] = max(lazyMax[iNoeud], val); lazyMin[iNoeud] = max(lazyMin[iNoeud], val);} void changeMin(int iNoeud, int val){ lazyMin[iNoeud] = min(lazyMin[iNoeud], val); lazyMax[iNoeud] = min(lazyMax[iNoeud], val);} void pushDown(int iNoeud){ segVal[iNoeud] = max(segVal[iNoeud], lazyMax[iNoeud]); segVal[iNoeud] = min(segVal[iNoeud], lazyMin[iNoeud]); if (iDeb[iNoeud] < iFin[iNoeud]) { changeMax(2*iNoeud, lazyMax[iNoeud]); changeMin(2*iNoeud, lazyMin[iNoeud]); changeMax(2*iNoeud+1, lazyMax[iNoeud]); changeMin(2*iNoeud+1, lazyMin[iNoeud]); } lazyMax[iNoeud] = 0, lazyMin[iNoeud] = INF;} int getVal(int iNoeud, int pos){ pushDown(iNoeud); if (iDeb[iNoeud] > pos or iFin[iNoeud] < pos) return 0; if (iDeb[iNoeud] == iFin[iNoeud]) return segVal[iNoeud]; return getVal(2*iNoeud, pos) + getVal(2*iNoeud+1, pos);} void update(int iNoeud, int deb, int fin, int op, int val){ pushDown(iNoeud); if (deb > iFin[iNoeud] or fin < iDeb[iNoeud]) return; if (deb <= iDeb[iNoeud] and iFin[iNoeud] <= fin) { if (op==1) lazyMax[iNoeud] = val; else lazyMin[iNoeud] = val; pushDown(iNoeud); return ; } update(2*iNoeud, deb, fin, op, val); update(2*iNoeud+1, deb, fin, op, val);} void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ buildTree(1, 0, n-1); for (int i(0); i < k; ++i) update(1, left[i], right[i], op[i], height[i]); for (int i(0); i < n; ++i) finalHeight[i] = getVal(1, i); return;}