| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 425227 | bipartite_matching | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define forint(i, N) for (int i = 0; i < (N); i++)
using namespace std;
vector<int> mintree(10000000, 0);
vector<int> maxtree(10000000, 0);
void updatemin(int node, int a, int b, int x, int y, int k) {
if (a <= x && y <= b) {
mintree[node] = k;
if (maxtree[node] < mintree[node]) {
maxtree[node] = k;
}
if (mintree[node * 2 + 1] < mintree[node]) {
mintree[node * 2 + 1] = mintree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
maxtree[node * 2 + 1] = mintree[node * 2 + 1];
}
}
if (mintree[node * 2 + 2] < mintree[node]){
mintree[node * 2 + 2] = mintree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
maxtree[node * 2 + 2] = mintree[node * 2 + 2];
}
}
return;
}
if (mintree[node * 2 + 1] < mintree[node]) {
mintree[node * 2 + 1] = mintree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
maxtree[node * 2 + 1] = mintree[node * 2 + 1];
}
}
if (mintree[node * 2 + 2] < mintree[node]){
mintree[node * 2 + 2] = mintree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
maxtree[node * 2 + 2] = mintree[node * 2 + 2];
}
}
if ((x + y) / 2 >= a) {
updatemin(node * 2 + 1, a, b, x, (x + y) / 2, k);
}
if ((x + y) / 2 + 1 <= b) {
updatemin(node * 2 + 2, a, b, (x + y) / 2 + 1, y, k);
}
maxtree[node] = max(maxtree[node * 2 + 1], maxtree[node * 2 + 2]);
mintree[node] = min(mintree[node * 2 + 1], mintree[node * 2 + 2]);
if (maxtree[node] < mintree[node]) {
maxtree[node] = mintree[node];
}
}
void updatemax(int node, int a, int b, int x, int y, int k) {
if (a <= x && y <= b) {
maxtree[node] = k;
if (maxtree[node] < mintree[node]) {
mintree[node] = k;
}
if (maxtree[node * 2 + 1] > maxtree[node]) {
maxtree[node * 2 + 1] = maxtree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
mintree[node * 2 + 1] = maxtree[node * 2 + 1];
}
}
if (maxtree[node * 2 + 2] > maxtree[node]) {
maxtree[node * 2 + 2] = maxtree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
mintree[node * 2 + 2] = maxtree[node * 2 + 2];
}
}
return;
}
if (maxtree[node * 2 + 1] > maxtree[node]) {
maxtree[node * 2 + 1] = maxtree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
mintree[node * 2 + 1] = maxtree[node * 2 + 1];
}
}
if (maxtree[node * 2 + 2] > maxtree[node]) {
maxtree[node * 2 + 2] = maxtree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
mintree[node * 2 + 2] = maxtree[node * 2 + 2];
}
}
if ((x + y) / 2 >= a) {
updatemax(node * 2 + 1, a, b, x, (x + y) / 2, k);
}
if ((x + y) / 2 + 1 <= b) {
updatemax(node * 2 + 2, a, b, (x + y) / 2 + 1, y, k);
}
maxtree[node] = max(maxtree[node * 2 + 1], maxtree[node * 2 + 2]);
mintree[node] = min(mintree[node * 2 + 1], mintree[node * 2 + 2]);
if (maxtree[node] < mintree[node]) {
mintree[node] = maxtree[node];
}
}
int pos = 0;
vector<int> heightfinal;
void search(int node, int x, int y, int target) {
if (mintree[node] == maxtree[node]) {
for (int i = target; i <= y; i++) {
heightfinal[i] = mintree[node];
}
pos = y + 1;
return;
}
if (mintree[node * 2 + 1] < mintree[node]) {
mintree[node * 2 + 1] = mintree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) maxtree[node * 2 + 1] = mintree[node * 2 + 1];
}
if (mintree[node * 2 + 2] < mintree[node]) {
mintree[node * 2 + 2] = mintree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) maxtree[node * 2 + 2] = mintree[node * 2 + 2];
}
if (maxtree[node * 2 + 1] > maxtree[node]) {
maxtree[node * 2 + 1] = maxtree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) mintree[node * 2 + 1] = maxtree[node * 2 + 1];
}
if (maxtree[node * 2 + 2] > maxtree[node]) {
maxtree[node * 2 + 2] = maxtree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) mintree[node * 2 + 2] = maxtree[node * 2 + 2];
}
if ((x + y) / 2 >= target) {
search(node * 2 + 1, x, (x + y) / 2, target);
}
else {
search(node * 2 + 2, (x + y) / 2 + 1, y, target);
}
}
void buildWall(int n, int k, vector<int> op, vector<int> left, vector<int> right, vector<int> height, vector<int> finalHeight) {
forint(i, k) {
if (op[i] == 1) {
updatemin(0, left[i], right[i], 0, n - 1, height[i]);
}
else {
updatemax(0, left[i], right[i], 0, n - 1, height[i]);
}
}
heightfinal.resize(n);
while (pos < n) {
//cerr << "hello" << endl;
search(0, 0, n - 1, pos);
}
finalHeight = heightfinal;
}