제출 #653761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653761		Lobo	Wall (IOI14_wall)	C++17	0 / 100	644 ms	182636 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e6+10;
const int inf = 1e9+10;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

int n, trt[4*maxn], trb[4*maxn];
pair<int,int> trmnb[4*maxn], trmxt[4*maxn];
vector<int> qrsin[maxn], qrsout[maxn];

void build(int no, int l, int r) {
    trt[no] = inf;
    trb[no] = -inf;
    trmxt[no] = mp(-inf,-1);
    trmnb[no] = mp(inf,-1);
    if(l == r) return;
    int f1=2*no,f2=2*no+1,mid=(l+r)/2;
    build(f1,l,mid);
    build(f2,mid+1,r);
}

void att(int no, int l, int r, int pos, pair<int,int> mxt, pair<int,int> mnb) {
    if(l > pos || r < pos) return;
    if(l == r) {
        trmxt[no] = mxt;
        trmnb[no] = mnb;
        return;
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    att(f1,l,mid,pos,mxt,mnb);
    att(f2,mid+1,r,pos,mxt,mnb);
    trmxt[no] = max(trmxt[f1],trmxt[f2]);
    trmnb[no] = min(trmnb[f1],trmnb[f2]);
}

// find the smallest i such that sfmnt[i] > sfmxb[i]
pair<pair<int,int>,pair<int,int>> findsf(int no, int l, int r, pair<int,int> mxt, pair<int,int> mnb) {
    if(l == r) {
        // cout << l << " - " << r << " " << valt << " , " << trt[no] << " " << valb << " , " << trb[no] << endl;
        // if(max(mxt,trmxt[no]) <= min(mnb,trmnb[no])) return l;
        // else return l+1;
        if(max(mxt,trmxt[no]) <= min(mnb,trmnb[no])) return mp(max(mxt,trmxt[no]),min(mnb,trmnb[no]));
        else return mp(mxt,mnb);
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    if(max(mxt,trmxt[f2]) <= min(mnb,trmnb[f2])) return findsf(f1,l,mid,max(mxt,trmxt[f2]), min(mnb,trmnb[f2]));
    else return findsf(f2,mid+1,r,mxt,mnb);
}

void buildWall(int32_t N, int32_t k, int32_t op[], int32_t left[], int32_t right[], int32_t height[], int32_t finalHeight[]){
    n = N;
    for(int i = 0; i < k; i++) {
        qrsin[left[i]].pb(i);
        qrsout[right[i]].pb(i);
    }

    build(1,0,k);
    set<int> st;
    att(1,0,k,0,mp(0,0),mp(inf,-1));
    for(int i = 0; i < n; i++) {
        for(auto j : qrsin[i]) {
            st.insert(j);
            // cout << "  " << j << endl;
            if(op[j] == 1) att(1,0,k,j+1,mp(height[j],j),mp(inf,-1));
            if(op[j] == 2) att(1,0,k,j+1,mp(-inf,-1),mp(height[j],j));
        }
        auto aux = findsf(1,0,k-1,mp(-inf,-1),mp(inf,-1));
        auto mxt = aux.fr;
        auto mnb = aux.sc; 
        if(mxt.sc == -1) finalHeight[i] = mnb.fr;
        else if(mnb.sc == -1) finalHeight[i] = mxt.fr;
        else if(mxt.sc < mnb.sc) finalHeight[i] = mxt.fr;
        else finalHeight[i] = mnb.fr;

        // finalHeight[i] = height[*st.lower_bound(x)];
        for(auto j : qrsout[i]) {
            st.erase(j);
            if(op[j] == 1) att(1,0,k,j+1,mp(-inf,-1),mp(inf,-1));
            if(op[j] == 2) att(1,0,k,j+1,mp(-inf,-1),mp(inf,-1));
        }
    }
}

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