oj.uz

Submission #586487

# Submission time Handle Problem Language Result Execution time Memory
586487 2022-06-30T10:37:03 Z wdjpng Meetings (IOI18_meetings) C++17
36 / 100
 525 ms 404940 KB 
#include "meetings.h"
#include <bits/stdc++.h>


#define int long long
#define all(a) a.begin(), a.end()
#define rep(i,n) for(int i = 0; i<n; i++)

using namespace std;

struct s
{
  int m=0,l=0,r=0, ar=0;
};

s unite(s s1, s s2)
{
  s res;
  res.ar=s1.ar+s2.ar;
  res.m=max({s1.m,s2.m,s1.r+s2.l});

  res.l=s1.l;
  res.r=s2.r;
  if(s1.l==s1.ar) res.l+=s2.l;
  if(s2.r==s2.ar) res.r+=s1.r;
  return res;
}

s def=s();
int N = 100000;
vector<s>T(4*N);

s update(int i, int l, int r, int ui, int uv)
{
  if(l>ui||r<=ui) return T[i];
  if(l+1==r) return T[i]=s({uv,uv,uv,1});
  return T[i] = unite(update(2*i,l,(l+r)/2,ui,uv), update(2*i+1,(l+r)/2,r,ui,uv));
}

s query(int i, int l, int r, int ql, int qr)
{
  if(l>=qr||r<=ql) return def;
  if(l>=ql&&r<=qr) return T[i];
  return unite(query(2*i,l,(l+r)/2,ql,qr),query(2*i+1,(l+r)/2,r,ql,qr));
}

vector<int> minimum_costs(vector<signed> H,vector<signed> L,
                                    vector<signed> R) {
  int n = H.size();
  if(n>5000)
  {
     rep(i,n) update(1,0,n,i,H[i]==1);
    vector<int>C(L.size());
    rep(cq, L.size()) C[cq]=2*(R[cq] - L[cq] + 1) - query(1,0,n,L[cq], R[cq]+1).m;
    return C;
  } else
  {
    vector<vector<int>>lef(n, vector<int>(n)), ri(n, vector<int>(n));
    rep(i,n)
    {
      int sum=0;
      vector<int>v, occ;
      for(int j = i; j < n; j++)
      {
        sum+=H[j];
        int c = 1;
        while (v.size()&&v[v.size()-1]<H[j])
        {
          sum+=(H[j]-v[v.size()-1])*occ[occ.size()-1];
          c+=occ[occ.size()-1];
          v.pop_back();
          occ.pop_back();
        }
        if(v.size()&&v[v.size()-1]==H[j]) occ[occ.size()-1]+=c;
        else {v.push_back(H[j]); occ.push_back(c);}
        lef[i][j]=sum;
      }
    } 
    for(int i = n-1; i >= 0; i--)
      {
        int sum=0;
        vector<int>v, occ;
        for(int j = i; j >= 0; j--)
        {
          sum+=H[j];
          int c = 1;
          while (v.size()&&v[v.size()-1]<H[j])
          {
            sum+=(H[j]-v[v.size()-1])*occ[occ.size()-1];
            c+=occ[occ.size()-1];
            v.pop_back();
            occ.pop_back();
          }
          if(v.size()&&v[v.size()-1]==H[j]) occ[occ.size()-1]+=c;
          else {v.push_back(H[j]); occ.push_back(c);}
          ri[i][j]=sum;
        }
      }
      vector<int>c(L.size());
      rep(i,L.size())
      {
        int minn=1e18;
        for(int j = L[i]; j <= R[i]; j++) {
          minn=min(minn, lef[L[i]][j]+ri[R[i]][j]-H[j]);
        }
        c[i]=minn;
      } 
      return c;
  }
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:7:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i,n) for(int i = 0; i<n; i++)
......
   54 |     rep(cq, L.size()) C[cq]=2*(R[cq] - L[cq] + 1) - query(1,0,n,L[cq], R[cq]+1).m;
      |         ~~~~~~~~~~~~              
meetings.cpp:54:5: note: in expansion of macro 'rep'
   54 |     rep(cq, L.size()) C[cq]=2*(R[cq] - L[cq] + 1) - query(1,0,n,L[cq], R[cq]+1).m;
      |     ^~~
meetings.cpp:7:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i,n) for(int i = 0; i<n; i++)
......
  100 |       rep(i,L.size())
      |           ~~~~~~~~~~              
meetings.cpp:100:7: note: in expansion of macro 'rep'
  100 |       rep(i,L.size())
      |       ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 174 ms 153960 KB Output is correct
3 Correct 171 ms 154028 KB Output is correct
4 Correct 172 ms 154032 KB Output is correct
5 Correct 179 ms 154036 KB Output is correct
6 Correct 141 ms 154028 KB Output is correct
7 Correct 170 ms 154032 KB Output is correct
8 Correct 122 ms 153968 KB Output is correct
9 Correct 120 ms 153968 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 174 ms 153960 KB Output is correct
3 Correct 171 ms 154028 KB Output is correct
4 Correct 172 ms 154032 KB Output is correct
5 Correct 179 ms 154036 KB Output is correct
6 Correct 141 ms 154028 KB Output is correct
7 Correct 170 ms 154032 KB Output is correct
8 Correct 122 ms 153968 KB Output is correct
9 Correct 120 ms 153968 KB Output is correct
10 Correct 515 ms 404900 KB Output is correct
11 Correct 520 ms 404856 KB Output is correct
12 Correct 523 ms 404940 KB Output is correct
13 Correct 525 ms 404864 KB Output is correct
14 Correct 381 ms 404860 KB Output is correct
15 Correct 428 ms 404864 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 46 ms 14292 KB Output is correct
3 Correct 135 ms 16156 KB Output is correct
4 Correct 132 ms 16204 KB Output is correct
5 Correct 107 ms 16188 KB Output is correct
6 Correct 137 ms 16332 KB Output is correct
7 Correct 137 ms 16300 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 46 ms 14292 KB Output is correct
3 Correct 135 ms 16156 KB Output is correct
4 Correct 132 ms 16204 KB Output is correct
5 Correct 107 ms 16188 KB Output is correct
6 Correct 137 ms 16332 KB Output is correct
7 Correct 137 ms 16300 KB Output is correct
8 Incorrect 144 ms 16208 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 174 ms 153960 KB Output is correct
3 Correct 171 ms 154028 KB Output is correct
4 Correct 172 ms 154032 KB Output is correct
5 Correct 179 ms 154036 KB Output is correct
6 Correct 141 ms 154028 KB Output is correct
7 Correct 170 ms 154032 KB Output is correct
8 Correct 122 ms 153968 KB Output is correct
9 Correct 120 ms 153968 KB Output is correct
10 Correct 515 ms 404900 KB Output is correct
11 Correct 520 ms 404856 KB Output is correct
12 Correct 523 ms 404940 KB Output is correct
13 Correct 525 ms 404864 KB Output is correct
14 Correct 381 ms 404860 KB Output is correct
15 Correct 428 ms 404864 KB Output is correct
16 Correct 6 ms 12756 KB Output is correct
17 Correct 46 ms 14292 KB Output is correct
18 Correct 135 ms 16156 KB Output is correct
19 Correct 132 ms 16204 KB Output is correct
20 Correct 107 ms 16188 KB Output is correct
21 Correct 137 ms 16332 KB Output is correct
22 Correct 137 ms 16300 KB Output is correct
23 Incorrect 144 ms 16208 KB Output isn't correct
24 Halted 0 ms 0 KB -