제출 #899777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899777		ByeWorld	벽 (IOI14_wall)	C++14	61 / 100	311 ms	43504 KiB

wall

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 3e5+20;
const int LOG = 60;
const int MOD = 998244353;
const int SQRT = 520;
const int INF = 2e9+10;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
 
int n, q;
int ans[MAXN];

struct node {
    int laz;
    int mn, mx;
} st[4*MAXN];

struct segtree {
    void merge(int id){
        // mx
        st[id].mx = max(st[lf].mx, st[rg].mx);
        st[id].mn = min(st[lf].mn, st[rg].mn);
        st[id].laz = -1;
    }
    void bd(int id, int l, int r){
        st[id].laz = -1;
        if(l==r){
            st[id].mn = st[id].mx = 0;
            return;
        }
        bd(lf, l, md); bd(rg, md+1, r);
        merge(id);
    }
    void push(int id, int l, int r, int p){
        st[id].mx = st[id].mn = p; 
        st[id].laz = p;
    }
    void bnc(int id, int l, int r){
        if(l==r || st[id].laz == -1) return;
        push(lf, l, md, st[id].laz);
        push(rg, md+1, r, st[id].laz);
        st[id].laz = -1;
    }
    void CHMX(int id, int l, int r, int x, int y, int p){
        if(r<x || y<l || st[id].mn >= p) return;
        if(x<=l && r<=y && st[id].mx <= p){ // keganti semua
            push(id, l, r, p); return;
        }
        bnc(id, l, r);
        CHMX(lf, l, md, x, y, p); CHMX(rg, md+1, r, x, y, p);
        merge(id);
    }
    void CHMN(int id, int l, int r, int x, int y, int p){
        if(r<x || y<l || st[id].mx <= p) return;
        if(x<=l && r<=y && st[id].mn >= p){ // keganti semua
            push(id, l, r, p); return;
        }
        bnc(id, l, r);
        CHMN(lf, l, md, x, y, p); CHMN(rg, md+1, r, x, y, p);
        merge(id);
    }
    
    void que(int id, int l, int r){
        if(l==r){ ans[l] = st[id].mx; return; }
        bnc(id, l, r);
        que(lf, l, md); que(rg, md+1, r);
    }
} A;

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    n = N;
    A.bd(1, 1, n);
    for(int i=0; i<k; i++){
        left[i]++; right[i]++;
        if(op[i]==1){ // a[i] = max(a[i], x)
            A.CHMX(1, 1, n, left[i], right[i], height[i]);
        } else {
            A.CHMN(1, 1, n, left[i], right[i], height[i]);
        }
    }
    A.que(1, 1, n);
    for(int i=0; i<n; i++) finalHeight[i] = ans[i+1];
    return;
}

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