제출 #836702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836702		IS_Rushdi	모임들 (IOI18_meetings)	C++17	19 / 100	677 ms	786432 KiB

meetings

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

struct item{
    long long l,r,m;
};
struct segment_tree{
    vector<vector<item>>st;
    vector<vector<pair<long long,long long>>>range;
    segment_tree(long long n,vector<int>a){
        long long q = 0;
        for(long long i = 1; ; i+=i){
            if(i >= n){
                st.assign(log2(i)+1,vector<item>());
                range.assign(log2(i)+1,vector<pair<long long,long long>>());
                long long q = i;
                for(long long 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(long long i = 0; i < st[0].size(); i++){
            range[0][i].first = i;
            range[0][i].second = i;
        }
        for(long long 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(long long i = 1; i < st.size(); i++){
            for(long long 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;
                long long x = range[i-1][j*2].second-range[i-1][j*2].first+1;
                long long 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.l + node2.l;
                }
                if(node2.r == x2){
                    st[i][j].r = node1.r + node2.r;
                }
                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;
            }
        }
    }
    long long findl(long long left,long long right,long long i,long long j){
        if(i < 0) return 0;
        long long l = range[i][j].first;
        long long r = range[i][j].second;
        if(l >= left && right >= r) return st[i][j].l;
        else findl(left,right,i-1,j*2);
    }
    long long findr(long long left,long long right,long long i,long long j){
        if(i < 0) return 0;
        long long l = range[i][j].first;
        long long r = range[i][j].second;
        if(l >= left && right >= r) return st[i][j].r;
        else findr(left,right,i-1,j*2+1);
    }
    long long find(long long left,long long right,long long i=-1,long long j=-1){
        if(i == -1){
            i = st.size()-1;
            j = 0;
        }
        long long l = range[i][j].first;
        long long r = range[i][j].second;
         long long ans = findl(left,right,i-1,j*2+1)+findr(left,right,i-1,j*2);
        if(l > right || r < left) return ans;
        else if(l >= left && r <= right){
            ans = max(ans,st[i][j].m);
            return ans;
        }
        else{
            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) {
  long long q = L.size();
  long long n = H.size();
  if(n <= 5000 && q <= 5000) return task(H,L,R);
  vector<long long> ans(q);
  segment_tree st(n,H);
  for(long long v = 0; v < q; v++){
    long long l = L[v];
    long long r = R[v];
    ans[v] = (2*(r-l+1))-st.find(l,r);
  }
  return ans;
}
// int main(){
//     long long n,m; cin >> n >> m;
//     vector<int>a(n);
//     vector<int>b(m),c(m);
//     for(long long i = 0; i < n; i++) cin >> a[i];
//     for(long long i = 0; i < m; i++) cin >> b[i] >> c[i];
//     vector<long long>ans = minimum_costs(a,b,c);
//     for(long long i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
// }   

컴파일 시 표준 에러 (stderr) 메시지

meetings.cpp: In constructor 'segment_tree::segment_tree(long long int, std::vector<int>)':
meetings.cpp:18:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<item> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |                 for(long long j = 0; j < st.size(); j++){
      |                                      ~~^~~~~~~~~~~
meetings.cpp:27:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(long long i = 0; i < st[0].size(); i++){
      |                              ~~^~~~~~~~~~~~~~
meetings.cpp:36:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<item> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(long long i = 1; i < st.size(); i++){
      |                              ~~^~~~~~~~~~~
meetings.cpp:37:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for(long long j = 0; j < st[i].size(); j++){
      |                                  ~~^~~~~~~~~~~~~~
meetings.cpp:12:19: warning: unused variable 'q' [-Wunused-variable]
   12 |         long long q = 0;
      |                   ^
meetings.cpp: In member function 'long long int segment_tree::findl(long long int, long long int, long long int, long long 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 'long long int segment_tree::findr(long long int, long long int, long long int, long long 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