Submission #138297

#	Time	Username	Problem	Language	Result	Execution time	Memory
138297		Angelos	Meetings (IOI18_meetings)	C++14	0 / 100	2 ms	376 KiB

meetings

//#include "meetings.h"
#include <iostream>
#include <vector>
#define l 2*cur
#define r ((2*cur)+1)
#define mid ((a+b)/2)
#define MAXN 100100

using namespace std;
typedef long long ll;
struct str{
    int mx;
    int mxl;
    int mxr;
    int all;
}tree[4*MAXN];

vector<int> H;

str doleaf(int o){
    str ret;
    if(o == 1){
        ret.mx = 1;
        ret.mxl = 1;
        ret.mxr = 1;
        ret.all = 1;
    }
    else{
        ret.mx = 0;
        ret.mxl = 0;
        ret.mxr = 0;
        ret.all = 0;
    }

    return ret;
}

str mergee(str ll , str rr){
    str ret;
    if(ll.all && rr.all) ret.all = 1;
    else ret.all = 0;

    if(ll.all) ret.mxl = ll.mxl + rr.mxl;
    else ret.mxl = ll.mxl;

    if(rr.all) ret.mxr = ll.mxr + rr.mxr;
    else ret.mxr = rr.mxr;

    ret.mx = max(ll.mxr + rr.mxl , max(ll.mx , rr.mx));

    return ret;
}

void build(int cur , int a , int b){
    if(a == b){
        //cout <<cur << " " <<  a << " " << H[a] << endl;
        tree[cur] = doleaf(H[a]);
        return;
    }

    build(l , a , mid);
    build(r , mid+1 , b);

    tree[cur] = mergee(tree[l] , tree[r]);
}

str query(int cur , int a , int b , int i , int j){
    if(a >= i && b<=j) return tree[cur];
    if(mid < i) return query(r , mid+1, b , i , j);
    if(mid+1 > j) return query(l ,a , mid , i , j);

    str qq1 = query(l ,a , mid , i , j) , qq2 = query(r , mid+1 , b , i , j);
    return mergee(qq1,qq2);
}

std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> L,
                                     std::vector<int> R) {
  H = h;
  int N = h.size();
  int Q = L.size();
  std::vector<long long> C(Q);

  build(1,0,N-1);
  //for(int i=0; i<4*N; i++) {cout << i << " ";}
  //cout << endl;

  //for(int i=0; i<4*N; i++) cout << tree[i].mx << " " ;

  for (int j = 0; j < Q; ++j) {
    int hh = query(1 , 0 , N-1 , L[j] , R[j]).mx;
    C[j]= (ll)(hh + (R[j] - L[j] + 1 - hh)*2);
    if(R[j] == L[j]) C[j] = 0;
  }
  return C;
}

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