제출 #823365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823365		Dremix10	모임들 (IOI18_meetings)	C++17	17 / 100	678 ms	9300 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const int N = 1e5+5;
const ll INF = 1e18+5;
const int MOD = 1e9+7;

int A[N],seg[4*N];

void build(int s, int e, int idx){
    if(s==e){
        seg[idx] = A[s];
        return;
    }
    int mid = (s+e)/2;
    build(s,mid,idx*2);
    build(mid+1,e,idx*2+1);
    seg[idx] = max(seg[idx*2],seg[idx*2+1]);
}

int query(int s, int e, int idx, int qs, int qe){
    if(qs<=s && e<=qe)return seg[idx];
    if(s > qe || e < qs)return 0;
    int mid = (s+e)/2;
    return max(query(s,mid,idx*2,qs,qe),query(mid+1,e,idx*2+1,qs,qe));
}


vector<long long> minimum_costs(vector<int> arr, vector<int> L, vector<int> R) {
    int n = arr.size();
    int q = L.size();
    int i,j,k;

    vector<ll> ans(q);

    // good i is always local minima
    //if(i-1 >= x && arr[i-1] < arr[i] || i+1 <= y && arr[i+1] < arr[i])continue;
    
    int cnt = 0;
    pi range[n];

    for(i=0;i<n;i++){
        if(arr[i] == 2){
            int temp = cnt;
            int j = i-1;
            while(temp--){
                A[j] = cnt;
                range[j] = {j-temp,i-1};
                j--;
            }
            cnt = 0;
            A[i] = 0;
        }
        else
            cnt++;
    }

    int temp = cnt;
    j = n-1;
            while(temp--){
                A[j] = cnt;
                range[j] = {j-temp,n-1};
                j--;
            }
            cnt = 0;
            //A[i] = 0;
    
    for(i=0;i<n;i++){
        cerr<<A[i]<<" ";
    }cerr<<endl;

    for(i=0;i<n;i++){
        cerr<<range[i].F<<"-"<<range[i].S<<"  ";
    }cerr<<endl;

    build(0,n-1,1);

    for(k=0;k<q;k++){
        int x = L[k];
        int y = R[k];

        int qx = x;
        int qy = y;
        int p1,p2;
        p1 = p2 = 0;
        if(A[x] > 0){
            qx = min(y,range[x].S)+1;
            p1 = qx - x;
        }

        if(A[y] > 0){
            qy = max(x,range[y].F)-1;
            p2 = y - qy;
        }


        ll maxi = max({p1,p2,query(0,n-1,1,qx,qy)});
        
        
        ll res = (y-x+1)*2 - maxi;
        
        ans[k] = res;
    }


    return ans;
}

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