Submission #795668

#	Time	Username	Problem	Language	Result	Execution time	Memory
795668		chanhchuong123	Wall (IOI14_wall)	C++14	100 / 100	574 ms	77316 KiB

wall

//#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 7;
const int MAX = 2000020;
int n, h[MAX], ans[MAX];
pair<int, int> st[MAX << 2];

void build(int id, int l, int r) {
    st[id] = make_pair(-INF, INF);
    if (l == r) {
        st[id] = make_pair(h[l], h[l]);
        return;
    }
    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}

void update(int id, int l, int r) {
    if (st[id].first > r) st[id] = make_pair(r, r); else
    if (st[id].second < l) st[id] = make_pair(l, l); else
    st[id] = make_pair(max(l, st[id].first), min(r, st[id].second));
}

void push(int id) {
    update(id << 1, st[id].first, st[id].second);
    update(id << 1 | 1, st[id].first, st[id].second); st[id] = make_pair(-INF, INF);
}

void update(int id, int l, int r, int u, int v, int t, int newH) {
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
        if (!t) update(id, newH, INF);
        else update(id, -INF, newH);
        return;
    }
    int mid = l + r >> 1; push(id);
    update(id << 1, l, mid, u, v, t, newH);
    update(id << 1 | 1, mid + 1, r, u, v, t, newH);
}

void magic(int id, int l, int r) {
    if (l == r) {
        ans[l] = st[id].first;
        return;
    }
    int mid = l + r >> 1; push(id);
    magic(id << 1, l, mid); magic(id << 1 | 1, mid + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	build(1, 1, n);
	for (int i = 0; i < k; i++) {
		update(1, 1, n, left[i] + 1, right[i] + 1, op[i] - 1, height[i]);
	}
	magic(1, 1, n);
	for (int i = 0; i < n; ++i)
        finalHeight[i] = ans[i + 1];
}

//int main(void) {
//    n = 10;
//    update(1, 1, n, 2, 9, 0, 4);
//    update(1, 1, n, 5, 10, 1, 1);
//    update(1, 1, n, 4, 7, 1, 5);
//    update(1, 1, n, 1, 6, 0, 3);
//    update(1, 1, n, 3, 3, 0, 5);
//    update(1, 1, n, 7, 8, 1, 0);
//    magic(1, 1, n);
//    for (int i = 1; i <= n; ++i) {
//        cout << ans[i] << ' ';
//    }
//}

Compilation message (stderr)

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:16:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid = l + r >> 1; push(id);
      |               ~~^~~
wall.cpp: In function 'void magic(int, int, int)':
wall.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int mid = l + r >> 1; push(id);
      |               ~~^~~

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39