oj.uz

Submission #836696

# Submission time Handle Problem Language Result Execution time Memory
836696 2023-08-24T14:13:35 Z IS_Rushdi Meetings (IOI18_meetings) C++17
19 / 100
 583 ms 786432 KB 
#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.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;
            }
        }
    }
    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;
        if(l > right || r < left) return 0;
        else if(l >= left && r <= right) return st[i][j].m;
        else{
            long long 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) {
  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] << ' ';
// }

Compilation message

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 156 ms 70868 KB Output is correct
3 Correct 160 ms 70900 KB Output is correct
4 Correct 156 ms 70868 KB Output is correct
5 Correct 158 ms 70860 KB Output is correct
6 Correct 161 ms 70904 KB Output is correct
7 Correct 167 ms 70900 KB Output is correct
8 Correct 159 ms 70868 KB Output is correct
9 Correct 164 ms 70868 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 156 ms 70868 KB Output is correct
3 Correct 160 ms 70900 KB Output is correct
4 Correct 156 ms 70868 KB Output is correct
5 Correct 158 ms 70860 KB Output is correct
6 Correct 161 ms 70904 KB Output is correct
7 Correct 167 ms 70900 KB Output is correct
8 Correct 159 ms 70868 KB Output is correct
9 Correct 164 ms 70868 KB Output is correct
10 Correct 559 ms 196544 KB Output is correct
11 Correct 580 ms 196428 KB Output is correct
12 Correct 563 ms 196424 KB Output is correct
13 Correct 583 ms 196300 KB Output is correct
14 Correct 560 ms 196516 KB Output is correct
15 Correct 565 ms 196300 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 351 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 351 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 156 ms 70868 KB Output is correct
3 Correct 160 ms 70900 KB Output is correct
4 Correct 156 ms 70868 KB Output is correct
5 Correct 158 ms 70860 KB Output is correct
6 Correct 161 ms 70904 KB Output is correct
7 Correct 167 ms 70900 KB Output is correct
8 Correct 159 ms 70868 KB Output is correct
9 Correct 164 ms 70868 KB Output is correct
10 Correct 559 ms 196544 KB Output is correct
11 Correct 580 ms 196428 KB Output is correct
12 Correct 563 ms 196424 KB Output is correct
13 Correct 583 ms 196300 KB Output is correct
14 Correct 560 ms 196516 KB Output is correct
15 Correct 565 ms 196300 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Runtime error 351 ms 786432 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -