Submission #836674

#	Time	Username	Problem	Language	Result	Execution time	Memory
836674		IS_Rushdi	Meetings (IOI18_meetings)	C++17	19 / 100	613 ms	196536 KiB

meetings

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

struct item{
    int l,r,m;
};
struct segment_tree{
    vector<vector<int>>st;
    vector<vector<pair<int,int>>>range;
    segment_tree(int n,vector<int>a){
        int q = 0;
        for(int i = 1; ; i+=i){
            if(i >= n){
                st.assign(log2(i)+1,vector<int>());
                range.assign(log2(i)+1,vector<pair<int,int>>());
                int q = i;
                for(int j = 0; j < st.size(); j++){
                    st[j].assign(q,0);
                    range[j].assign(q,{0,0});
                    q/=2;
                }
                q = i;
                break;
            }
        }
        for(int i = 0; i < st[0].size(); i++){
            range[0][i].first = i;
            range[0][i].second = i;
        }
        for(int i = 0; i < n; i++){
            st[0][i] = a[i];
        }
        for(int i = 1; i < st.size(); i++){
            for(int j = 0; j < st[i].size(); j++){
                int node1 = st[i-1][j*2];
                int node2 = st[i-1][j*2+1];
                st[i][j] = node1+node2;
                range[i][j].first = range[i-1][j*2].first;
                range[i][j].second = range[i-1][j*2+1].second;
            }
        }
    }
    int findL(int i,int j,int left,int right){
        if(i < 0) return 0;
        int l = range[i][j].first;
        int r = range[i][j].second;
        int x = r-l+1;
        if(l >= left && r <= right && x == st[i][j]) return x;
        else return findL(i-1,j*2,left,right);
    }
    int findR(int i,int j,int left,int right){
        if(i < 0) return 0;
        int l = range[i][j].first;
        int r = range[i][j].second;
        int x = r-l+1;
        if(l >= left && r <= right && st[i][j] == x) return st[i][j];
        else return findR(i-1,j*2+1,left,right);
    }
    int find(int left,int right,int i=-1,int j=-1){
        if(i == -1){
            i = st.size()-1;
            j = 0;
        }
        int l = range[i][j].first;
        int r = range[i][j].second;
        if(l > right || r < left) return 0;
        else{
            int ans = 0;
            if(l >= left && r <= right){
                ans = max(findR(i,j,left,right),findL(i,j,left,right));
            }else{
                ans = max(find(left,right,i-1,j*2+1),find(left,right,i-1,j*2));
            }
            ans = max(ans,findR(i-1,j*2,left,right)+findL(i-1,j*2+1,left,right));
            return ans;
        }
    }
};

vector<long long>task(vector<int> H, vector<int> L,vector<int> R){
  long long q = L.size();
  long long n = H.size();
  vector<long long > ans(q);
  vector<vector<long long >> mn(n,vector<long long>(n,1e18));
  for(long long i = 0; i < n; i++){
    mn[i][i] = H[i];
    long long curr = H[i];
    for(long long j = i-1; j >= 0; j--){
        curr = max(curr,H[j]*1ll);
        mn[j][i] = curr;
    }curr = H[i];
    for(long long j = i+1; j < n; j++){
        curr = max(curr,H[j]*1ll);
        mn[j][i] = curr;
    }
  }
 
  for(long long i = 0; i < n; i++){
    for(long long j = 1; j < n; j++){
        mn[j][i] += mn[j-1][i];
    }
  }
  for(long long v = 0; v < q; v++){
    long long l = L[v];
    long long r = R[v];
    long long cnt = 1e18;
    for(long long i = l; i <= r; i++){
        if(l == 0)cnt = min(cnt,mn[r][i]);
        else cnt = min(cnt,mn[r][i]-mn[l-1][i]);
    }
    ans[v] = cnt;
  }
  return ans;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
  int q = L.size();
  int n = H.size();
  if(n <= 5000 && q <= 5000) return task(H,L,R);
  vector<long long> ans(q);
  segment_tree st(n,H);
  for(int v = 0; v < q; v++){
    int l = L[v];
    int r = R[v];
    ans[v] = (2*(r-l+1))-st.find(l,r);
  }
  return ans;
}
// int main(){
//     int n,m; cin >> n >> m;
//     vector<int>a(n);
//     vector<int>b(m),c(m);
//     for(int i = 0; i < n; i++) cin >> a[i];
//     for(int i = 0; i < m; i++) cin >> b[i] >> c[i];
//     vector<long long>ans = minimum_costs(a,b,c);
//     for(int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
// }   

Compilation message (stderr)

meetings.cpp: In constructor 'segment_tree::segment_tree(int, std::vector<int>)':
meetings.cpp:18:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |                 for(int j = 0; j < st.size(); j++){
      |                                ~~^~~~~~~~~~~
meetings.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int i = 0; i < st[0].size(); i++){
      |                        ~~^~~~~~~~~~~~~~
meetings.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int i = 1; i < st.size(); i++){
      |                        ~~^~~~~~~~~~~
meetings.cpp:35:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(int j = 0; j < st[i].size(); j++){
      |                            ~~^~~~~~~~~~~~~~
meetings.cpp:12:13: warning: unused variable 'q' [-Wunused-variable]
   12 |         int q = 0;
      |             ^

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