Submission #1221012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221012		cpdreamer	모임들 (IOI18_meetings)	C++20	17 / 100	48 ms	8640 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = (ll)1e9+7;
#define P pair
#define F first
#define S second
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
int t[(int)1e5+1][18], a[(int)1e5+1];
void build(int n) {
    for(int i = 1; i <= n; ++i) t[i][0] = a[i];
    for(int k = 1; k < 18; ++k) {
        for(int i = 1; i + (1 << k) - 1 <= n; ++i) {
            t[i][k] = max(t[i][k - 1], t[i + (1 << (k - 1))][k - 1]);
        }
    }
}

int query(int l, int r) {
    int k = 31 - __builtin_clz(r - l + 1);
    return max(t[l][k], t[r - (1 << k) + 1][k]);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    int  q=(ll)L.size();
    int  n=(ll)H.size();
    V<int>v1;
    V<P<int,int>>v2;
    for (int i=0;i<n;i++) {
        if (H[i]==2) {
            v1.pb(i);
        }
    }
    for (int i=1;i<(int)v1.size();i++) {
        v2.pb({v1[i-1],v1[i]});
    }
    for (int i=0;i<(int)v2.size();i++) {
        a[i+1]=v2[i].S-v2[i].F-1;
    }
    V<ll>C;
    build((int)v2.size());
    for (int i=0;i<q;i++) {
        int l=L[i],r=R[i];
        int ans1=-1;
        int ans2=-1;
        int lb=0,rb=(int)v1.size()-1;
        while (lb<=rb) {
            int m=lb+(rb-lb)/2;
            if (v1[m]>=l) {
                ans1=m;
                rb=m-1;
            }
            else
                lb=m+1;
        }
        lb=0,rb=(int)v1.size()-1;
        while (lb<=rb) {
            int m=lb+(rb-lb)/2;
            if (v1[m]<=r) {
                ans2=m;
                lb=m+1;
            }
            else
                rb=m-1;
        }
        if (ans2==-1 ) {
            C.pb(r-l+1);
            continue;
        }
        if (v1[ans2]<l) {
            C.pb(r-l+1);
            continue;
        }
        int x=r-l+1+min(r-v1[ans1]+1,v1[ans2]-l+1);
        lb=ans1+1,rb=ans2;
        if (lb>rb) {
            C.pb(x);
            continue;
        }
        x=min(x,2*(r-l+1)-query(lb,rb));
        C.pb(x);
    }
    return C;
}

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