oj.uz

Submission #946631

# Submission time Handle Problem Language Result Execution time Memory
946631 2024-03-14T20:32:05 Z PagodePaiva Meetings (IOI18_meetings) C++17
0 / 100
 27 ms 2480 KB 
#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;
    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]));
      res.push_back(2*(y-x+1) - resp);
    }
    return res;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 27 ms 2480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 27 ms 2480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -