Submission #1237350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237350		dosts	Meetings (IOI18_meetings)	C++20	17 / 100	87 ms	16712 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 5e3+1, inf = 2e9;
vi h;

struct Node {
  int ans,pref,suf,sz;
};

Node merge(Node a,Node b) {
  Node ret;
  ret.ans = max({a.ans,b.ans,a.suf+b.pref});
  ret.pref = (a.pref == a.sz)?(a.pref+b.pref):a.pref;
  ret.suf = (b.suf == b.sz)?(a.suf+b.suf):b.suf;
  ret.sz = a.sz+b.sz;
  return ret;
}
struct ST {
  vector<Node> t;

  void build(int node,int l,int r) {
    if (l == r) {
      t[node] ={0,0,0,1};
      return;
    }
    int m = (l+r) >> 1;
    build(2*node,l,m),build(2*node+1,m+1,r);
    t[node] = merge(t[2*node],t[2*node+1]);
  }
  ST(int nn) {
    t.resize(4*nn+1);
    build(1,1,nn);
  }

  void update(int node,int l,int r,int p,int v) {
    if (!v) return;
    if (l == r) {
      t[node] = {1,1,1,1};
      return;
    }
    int m = (l+r) >> 1;
    if (p <= m) update(2*node,l,m,p,v);
    else update(2*node+1,m+1,r,p,v);
    t[node] = merge(t[2*node],t[2*node+1]);
  }

  Node query(int node,int l,int r,int L,int R) {
    if (l > R || r < L) return {0,0,0,1};
    if (l >= L && r <= R) return t[node];
    int m = (l+r) >> 1;
    return merge(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
  }
};

vi minimum_costs(std::vector<signed> H, std::vector<signed> L,
                                     std::vector<signed> R) {
    ST st(big(H));
    h = vi(all(H));
    for (int i = 0;i<big(H);i++) st.update(1,1,big(H),i+1,h[i] == 1);
    vi answer(big(L));
    for (int i = 0;i<big(L);i++) {
      answer[i] = 2*(R[i]-L[i]+1)-st.query(1,1,big(H),L[i]+1,R[i]+1).ans;
    }
    return answer;
}

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