제출 #609572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
609572		AmirElarbi	모임들 (IOI18_meetings)	C++14	0 / 100	1 ms	340 KiB

meetings

#include <bits/stdc++.h>
#define vi vector<int>
#define gi greater<int>
#define gr greater
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 1e9+7;
const int nax = 5005+5;
typedef complex<int> Point;
//#define X real()
//#define Y imag()
//#include "meetings.h"
ll st[nax*4], s[nax];
void build(int v, int l, int r){
    if(l == r){
        st[v] = s[l];
        return;
    }
    int md =(l+r)/2;
    build(v*2,l,md);
    build(v*2+1,md+1,r);
    st[v] = max(st[v*2], st[v*2+1]);
}
int query(int v, int l, int r, int i, int j){
    if(r < i || l > j) return 0;
    if(i <= l && r <= j) return st[v];
    int md = (l+r)/2;
    return max(query(v*2,l,md,i,j), query(v*2+1, md+1, r, i, j));
}
ve<ll> minimum_costs(vi h, vi l, vi r) {
    int n = h.size();
    vi ind;
    int cnt = 0;
    for (int i = 0; i < n; ++i)
    {
        if(h[i] == 1){
            cnt++;
        } else {
            if(cnt){
                ind.pb(i);
                s[i] = cnt;
            }
            cnt = 0;
        }
    }    
    build(1,0,n);
    if(cnt) {

        ind.pb(n);
    }
    int q = l.size();
    ve<ll> ans(q);
    for (int i = 0; i < q; ++i)
    {
        //cout << "YES" << i << endl;
        int st = *upper_bound(ind.begin(), ind.end(), l[i]), 
            nd = *upper_bound(ind.begin(), ind.end(), r[i]);
        int mx = 0; 
        if(st != nd){
            mx = max(min(st-l[i], query(1,0,n, st, st)), max(0, query(1,0,n, nd, nd) - (nd-r[i]-1)));
            st++,nd--;
            if(st <= nd){
                mx = max(mx, query(1,0,n,st,nd));
            }
        } else {
            mx = min(max(0, query(1,0,n, nd, nd) - (nd-r[i]-1)), r[i]-l[i]+1);
        }
        ans[i] = mx + ((r[i]-l[i]+1) - mx)*2;
    }
    return ans;
}

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