제출 #720405

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720405		RandomLB	벽 (IOI14_wall)	C++17	100 / 100	798 ms	107176 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef complex<ld> P;
#define ms(x, a) memset(x, a, sizeof(x))
#define siz(x) (int)x.size()
#define len(x) (int)x.length()
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define lzMx first
#define lzMn second
#define FOR(i,x) for (int i = 0; i < x; i++)
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vals, Args&&... values){
    cout << vals << " = ";
    string delim = "";
    (...,(cout << delim << values, delim = ", "));
    cout << endl;
}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;
//===========================================
const int MAX = 8e6+5;
pi st[MAX];
int res[MAX];

inline void chmax(int &a, int b){ a = max(a, b); }
inline void chmin(int &a, int b){ a = min(a, b); }

void prop(int i){
    for (int t = 2*i; t <= 2*i+1; t++){
        if (st[t].lzMx > st[i].lzMn) st[t] = {st[i].lzMn, st[i].lzMn};
        else if (st[t].lzMn < st[i].lzMx) st[t] = {st[i].lzMx, st[i].lzMx};
        else { chmax(st[t].lzMx, st[i].lzMx); chmin(st[t].lzMn, st[i].lzMn); }
    }
    st[i] = {0, INF};
}

void update(int i, int l, int r, int tl, int tr, int val, int c){
    if (l != r) prop(i);
    if (l > tr || r < tl) return;
    if (tl <= l && r <= tr){
       if (c == 1){ chmax(st[i].lzMx, val); chmax(st[i].lzMn, val); }
       else { chmin(st[i].lzMn, val); chmin(st[i].lzMx, val); }
       if (l != r) prop(i);
       return;
    }
    int m = l+(r-l)/2;
    update(2*i, l, m, tl, tr, val, c);
    update(2*i+1, m+1, r, tl, tr, val, c);
}

void walk(int i, int l, int r){
    if (l != r) prop(i);
    if (l == r){ res[l] = st[i].lzMx; return; }
    int m = l+(r-l)/2;
    walk(2*i, l, m); walk(2*i+1, m+1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < MAX; i++) st[i] = {0, INF};
    for (int i = 0; i < k; i++){
        left[i]++, right[i]++;
        update(1, 1, n, left[i], right[i], height[i], op[i]);
    }
    walk(1, 1, n);
    for (int i = 0; i < n; i++) finalHeight[i] = res[i+1];
}

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