제출 #288828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288828		Ozy	모임들 (IOI18_meetings)	C++17	17 / 100	160 ms	14308 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define debug(a) cerr << #a << " = " << a << endl
#define lli long long int

struct x{
    lli MAX;
    lli Mi;
    lli Md;
    lli hizq;
    lli hder;
};

x ST[2000000];
x act;
lli cont,n,q,res,dif;
vector<lli> total;

void creah(int pos) {

    ST[pos].hizq = cont++;
    ST[pos].hder = cont++;

}

void rango(lli nodo, lli ini, lli fin, lli l, lli r){
    lli mitad,tra;

    if (ini >= l && r >= fin) {
        if (act.MAX == -1) act = ST[nodo];
        else {

            act.MAX = max(act.MAX, ST[nodo].MAX);
            tra = act.Md + ST[nodo].Mi;
            act.MAX = max(act.MAX, tra);

            if (fin-ini+1 == ST[nodo].Md) act.Md += ST[nodo].Md;
            else act.Md = ST[nodo].Md;

        }
    }
    else if (ini > r || fin < l) return;
    else {

        mitad = (ini+fin) /2;
        if (ST[nodo].hizq == 0) creah(nodo);

        rango(ST[nodo].hizq,ini,mitad,l,r);
        rango(ST[nodo].hder,mitad+1,fin,l,r);
    }


}

void actualiza(lli nodo, lli ini, lli fin, lli des) {
    lli mitad,uni;

    if (ini == fin && ini == des) {
        ST[nodo].MAX = 1;
        ST[nodo].Mi = 1;
        ST[nodo].Md = 1;
    }
    else if (ini <= des && fin >= des) {
        mitad = (ini + fin) /2;

        if (ST[nodo].hizq == 0) creah(nodo);

        actualiza(ST[nodo].hizq,ini,mitad,des);
        actualiza(ST[nodo].hder,mitad+1,fin,des);

        ST[nodo].MAX = max(ST[ ST[nodo].hizq ].MAX, ST[ ST[nodo].hder ].MAX);
        uni = ST[ ST[nodo].hizq ].Md + ST[ ST[nodo].hder ].Mi;
        ST[nodo].MAX = max(uni, ST[nodo].MAX);

        if (mitad-ini+1 == ST[ ST[nodo].hizq ].Mi) ST[nodo].Mi = ST[ ST[nodo].hizq ].Mi + ST[ ST[nodo].hder ].Mi;
        else ST[nodo].Mi = ST[ ST[nodo].hizq ].Mi;

        if (fin-mitad == ST[ ST[nodo].hder ].Md) ST[nodo].Md = ST[ ST[nodo].hder ].Md + ST[ ST[nodo].hizq ].Md;
        else ST[nodo].Md = ST[ ST[nodo].hder ].Md;

    }

}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) {

    cont = 2;
    n = H.size();
    n--;
    q = L.size();

    rep (i,0,n) if (H[i] == 1) actualiza(1,0,n,i);


    rep(i,0,q-1) {

        act = {-1,-1,-1,-1,-1};

        rango(1,0,n,L[i],R[i]);
        res = act.MAX;

        dif = R[i] - L[i] + 1;
        res +=  2*(dif - res);
        total.push_back(res);

    }

    return total;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40