Submission #836694

#	Time	Username	Problem	Language	Result	Execution time	Memory
836694		IS_Rushdi	Meetings (IOI18_meetings)	C++17	19 / 100	592 ms	786432 KiB

meetings

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

struct item{
    int l,r,m;
};
struct segment_tree{
    vector<vector<item>>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<item>());
                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,0,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].l = (a[i]==1);
            st[0][i].r = (a[i]==1);
            st[0][i].m = (a[i]==1);
        }
        for(int i = 1; i < st.size(); i++){
            for(int j = 0; j < st[i].size(); j++){
                item node1 = st[i-1][j*2];
                item node2 = st[i-1][j*2+1];
                st[i][j].l = node1.l;
                st[i][j].r = node2.r;
                int x = range[i-1][j*2].second-range[i-1][j*2].first+1;
                int x2 = range[i-1][j*2+1].second-range[i-1][j*2+1].first+1;
                if(node1.l == x){
                    st[i][j].l = node1.m + node2.l;
                }
                if(node2.r == x2){
                    st[i][j].r = node1.r + node2.m;
                }
                st[i][j].m = max(node1.m,node2.m);
                st[i][j].m = max(st[i][j].m,node1.r+node2.l);
                st[i][j].m = max(st[i][j].m,st[i][j].l);
                st[i][j].m = max(st[i][j].m,st[i][j].r);
                range[i][j].first = range[i-1][j*2].first;
                range[i][j].second = range[i-1][j*2+1].second;
            }
        }
    }
    int findl(int left,int right,int i,int j){
        if(i < 0) return 0;
        int l = range[i][j].first;
        int r = range[i][j].second;
        if(l >= left && right >= r) return st[i][j].l;
        else findl(left,right,i-1,j*2);
    }
    int findr(int left,int right,int i,int j){
        if(i < 0) return 0;
        int l = range[i][j].first;
        int r = range[i][j].second;
        if(l >= left && right >= r) return st[i][j].r;
        else findr(left,right,i-1,j*2+1);
    }
    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 if(l >= left && r <= right) return st[i][j].m;
        else{
            int ans = findl(left,right,i-1,j*2+1)+findr(left,right,i-1,j*2);
            ans = max(ans,max(find(left,right,i-1,j*2+1),find(left,right,i-1,j*2)));
            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<item> >::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<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int i = 0; i < st[0].size(); i++){
      |                        ~~^~~~~~~~~~~~~~
meetings.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<item> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i = 1; i < st.size(); i++){
      |                        ~~^~~~~~~~~~~
meetings.cpp:37:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for(int j = 0; j < st[i].size(); j++){
      |                            ~~^~~~~~~~~~~~~~
meetings.cpp:12:13: warning: unused variable 'q' [-Wunused-variable]
   12 |         int q = 0;
      |             ^
meetings.cpp: In member function 'int segment_tree::findl(int, int, int, int)':
meetings.cpp:64:19: warning: control reaches end of non-void function [-Wreturn-type]
   64 |         else findl(left,right,i-1,j*2);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~
meetings.cpp: In member function 'int segment_tree::findr(int, int, int, int)':
meetings.cpp:71:19: warning: control reaches end of non-void function [-Wreturn-type]
   71 |         else findr(left,right,i-1,j*2+1);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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