Submission #587739

#	Time	Username	Problem	Language	Result	Execution time	Memory
587739		alireza_kaviani	Meetings (IOI18_meetings)	C++17	17 / 100	82 ms	9940 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define SZ(x)   int((x).size())
#define lc      id << 1
#define rc      lc | 1

const ll MAXN = 1e5 + 10;
const ll LOG = 22;
const ll INF = 1e18;

struct Node{
    int mx , pref , suff , sz;
};

int n , q , A[MAXN];
Node seg[MAXN << 2];

Node merge(const Node &L , const Node &R){
    if(L.sz == 0)   return R;
    if(R.sz == 0)   return L;
    Node ans;
    ans.mx = max(L.mx , R.mx);
    ans.mx = max(ans.mx , L.suff + R.pref);
    ans.sz = L.sz + R.sz;
    ans.pref = L.pref + (L.pref == L.sz ? R.pref : 0);
    ans.suff = R.suff + (R.suff == R.sz ? L.suff : 0);
    return ans;
}

void build(int id = 1 , int l = 0 , int r = n){
    if(r - l == 1){
        seg[id].sz = 1;
        if(A[l] == 1){
            seg[id].mx = seg[id].pref = seg[id].suff = 1;
        }
        return;
    }
    int mid = l + r >> 1;
    build(lc , l , mid);
    build(rc , mid , r);
    seg[id] = merge(seg[lc] , seg[rc]);
}

Node get(int ql , int qr , int id = 1 , int l = 0 , int r = n){
    if(qr <= l || r <= ql)  return Node();
    if(ql <= l && r <= qr)  return seg[id];
    int mid = l + r >> 1;
    return merge(get(ql , qr , lc , l , mid) , get(ql , qr , rc , mid , r));
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    n = SZ(H); q = SZ(L);
    if(n > MAXN){
        return {};
    }
    for(int i = 0 ; i < n ; i++){
        A[i] = H[i];
    }
    build();
    vector<ll> ans(q , 0);
    for(int i = 0 ; i < q ; i++){
        R[i]++;
        Node res = get(L[i] , R[i]);
        ans[i] = (R[i] - L[i]) * 2 - res.mx;
    }
    return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'void build(int, int, int)':
meetings.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int mid = l + r >> 1;
      |               ~~^~~
meetings.cpp: In function 'Node get(int, int, int, int, int)':
meetings.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = l + r >> 1;
      |               ~~^~~

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