제출 #1364554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364554		mariza	모임들 (IOI18_meetings)	C++20	17 / 100	52 ms	12460 KiB

meetings

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

typedef long long ll;
const ll INF=1e18;
const ll N=1e5;
#define MID ((l+r)/2)

ll b[N]={};
struct node{
    ll val;
    node *L, *R;

    void init(ll l, ll r){
        if(l==r) val=b[l];
        else{
            L=new node;
            L->init(l,MID);

            R=new node;
            R->init(MID+1,r);

            val=max(L->val,R->val);
        }
    }

    ll ans(ll l, ll r, ll tl, ll tr){
        if(tl<=l && r<=tr) return val;
        else if(r<tl || tr<l) return 0;
        else return max(L->ans(l,MID,tl,tr),R->ans(MID+1,r,tl,tr));
    }
};

vector<ll> minimum_costs(vector<int> a, vector<int> l, vector<int> r){
    ll n=a.size(), q=l.size();

    ll nxt[n], prev[n];
    ll curr=-1;
    for(ll i=0; i<n; i++){
        if(a[i]==2) curr=i;
        prev[i]=curr;
    }
    curr=n;
    for(ll i=n-1; i>=0; i--){
        if(a[i]==2) curr=i;
        nxt[i]=curr;
    }

    if(a[0]==1) b[0]=1;
    for(ll i=1; i<n; i++){
        if(a[i]==1) b[i]=b[i-1]+1;
    }

    node seg;
    seg.init(0,n-1);

    vector<ll> ans;
    for(ll i=0; i<q; i++){
        ans.push_back(2*(r[i]-l[i]+1)-max({seg.ans(0,n-1,nxt[l[i]],prev[r[i]]),min((ll)r[i]+1,nxt[l[i]])-l[i],r[i]-max((ll)l[i]-1,prev[r[i]])}));
    }

    return ans;
}

• 서브태스크 1: 0 / 4
• 서브태스크 2: 0 / 15
• 서브태스크 3: 17 / 17
• 서브태스크 4: 0 / 24
• 서브태스크 5: 0 / 40