제출 #713913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713913		alvingogo	모임들 (IOI18_meetings)	C++14	17 / 100	45 ms	15208 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct ST{
    vector<vector<int> > dp;
    void init(vector<int> x){
        int n=x.size();
        dp.resize(20,vector<int>(n));
        dp[0]=x;
        for(int i=1;i<20;i++){
            for(int j=0;j+(1<<(i-1))<n;j++){
                dp[i][j]=max(dp[i-1][j],dp[i-1][j+(1<<(i-1))]);
            }
        }
    }
    int query(int l,int r){
        if(l>r){
            return 0;
        }
        int x=__lg(r-l+1);
        return max(dp[x][l],dp[x][r-(1<<x)+1]);
    }

}szt;
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
    int n=h.size(),q=l.size();
    vector<long long> ans(q);
    vector<int> a(n,-1),b(n,-1);
    int c=-1;
    for(int i=0;i<n;i++){
        if(h[i]==1){
            if(c==-1){
                c=i;
            }
            a[i]=c;
        }
        else{
            c=-1;
        }
    }
    c=n;
    for(int i=n-1;i>=0;i--){
        if(h[i]==1){
            if(c==-1){
                c=i;
            }
            b[i]=c;
        }
        else{
            c=-1;
        }
    }
    vector<int> gg(n);
    for(int j=0;j<n;j++){
        if(h[j]==2){
            continue;
        }
        gg[j]=b[j]-a[j]+1;
    }
    szt.init(gg);
    for(int i=0;i<q;i++){
        int x=0;
        int u=l[i],v=r[i];
        if(h[l[i]]==1){
            x=max(x,b[l[i]]-l[i]+1);
            u=b[l[i]]+1;
        }
        if(h[r[i]]==1){
            x=max(x,r[i]-a[r[i]]+1);
            v=a[r[i]]-1;
        }
        x=max(x,szt.query(u,v));
        x=min(x,r[i]-l[i]+1);
        ans[i]=2*(r[i]-l[i]+1)-x;
    }
    return ans;
}

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