Submission #946639

#	Time	Username	Problem	Language	Result	Execution time	Memory
946639		PagodePaiva	모임들 (IOI18_meetings)	C++17	0 / 100	77 ms	4800 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define N 100010

using namespace std;

int v[N];

struct Segtree{
  int tree[4*N];
  int join(int a, int b){
    return max(a, b);
  }
  void build(int node, int l, int r){
    if(l == r){
      tree[node] = v[l];
      return;
    }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    tree[node] = join(tree[2*node], tree[2*node+1]);
    return;
  }
  int query(int node, int l, int r, int tl, int tr){
    if(l > r) return 0;
    if(l > tr or tl > r) return -1;
    if(l <= tl and tr <= r) return tree[node];
    int mid = (tl+tr)/2;
    return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
  }
} seg;

std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> ql,
                                     std::vector<int> qr) {
    int cnt = 0, idx = 1;
    vector <int> dois;
    dois.push_back(-1);
    int q = ql.size();
    int n = h.size();
    for(int i = 0;i < n;i++){
      if(h[i] == 1) cnt++;
      else{
        dois.push_back(i);
        v[idx] = cnt;
        cnt = 0;
        idx++;
      }
    }
    v[idx] = cnt;
    dois.push_back(n);
    seg.build(1, 1, idx);
    vector <ll> res;
    for(int i = 0;i < q;i++){
      int l = 1, r = idx;
      int x = ql[i], y = qr[i];
      while(l < r){
        int mid = (l+r)/2;
        if(dois[mid] < x) l = mid+1;
        else r = mid;
      }
      int dl = l;
      l = 1;
      r = idx;
      while(r-l > 1){
        int mid = (l+r)/2;
        if(dois[mid] > y) r = mid-1;
        else l = mid;
      }
      // cout << dois[r] << ' ' << y << endl;
      if(dois[r] > y) r = l;
      else l = r;
      int dr = l;
      // cout << dl << ' ' << dr << endl;
      int resp = seg.query(1, dl+1, dr, 1, idx);
      resp = max(resp, (dois[dl] > y ? 0 : dois[dl] -x));
      resp = max(resp, (dois[dr] < x ? 0 : y - dois[dr]));
      if(dois[dl] > y and dois[dr] < x) resp = y-x+1;
      res.push_back(2*(y-x+1) - resp);
    }
    return res;
}

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