Submission #609578

#	Time	Username	Problem	Language	Result	Execution time	Memory
609578		AmirElarbi	Meetings (IOI18_meetings)	C++14	0 / 100	45 ms	2248 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 = 1e5+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-1);
                s[i-1] = cnt;
            }
            cnt = 0;
        }
    }    
    ind.pb(n-1);
    s[n-1] = cnt;
    build(1,0,n-1);
    int q = l.size();
    ve<ll> ans(q);
    for (int i = 0; i < q; ++i)
    {
        //cout << "YES" << i << endl;
        int st = *lower_bound(ind.begin(), ind.end(), l[i]), 
            nd = *lower_bound(ind.begin(), ind.end(), r[i]);
        int mx = 0; 
        if(st != nd){
            mx = max(min(st-l[i]+1, query(1,0,n, st, st)), max(0, query(1,0,n, nd, nd) - (nd-r[i])));
            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])), 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