oj.uz

Submission #75486

# Submission time Handle Problem Language Result Execution time Memory
75486 2018-09-09T22:12:35 Z C_SUNSHINE Meetings (IOI18_meetings) C++14
19 / 100
 5500 ms 4868 KB 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include "meetings.h"
using namespace std;

typedef long long LL;

LL vl[750005],vr[750005];

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R)
{
  vector<LL> C;
  int Q=L.size();
  for(int qi=0;qi<Q;qi++)
  {
    int l=L[qi],r=R[qi];
    vector<int> st;
    st.clear();
    LL now=0;
    for(int i=l;i<=r;i++)
    {
      while(!st.empty()&&H[i]>H[st.back()])
      {
        if(st.size()==1)now-=((LL)st[0]-l+1)*H[st[0]];
        else now-=((LL)st[st.size()-1]-st[st.size()-2])*H[st.back()];
        st.pop_back();
      }
      if(st.size()==0)now+=((LL)i-l+1)*H[i];
      else now+=((LL)i-st.back())*H[i];
      st.push_back(i);
      vl[i]=now;
    }
    st.clear();
    now=0;
    for(int i=r;i>=l;i--)
    {
      while(!st.empty()&&H[i]>H[st.back()])
      {
        if(st.size()==1)now-=((LL)r-st[0]+1)*H[st[0]];
        else now-=((LL)st[st.size()-2]-st[st.size()-1])*H[st.back()];
        st.pop_back();
      }
      if(st.size()==0)now+=((LL)r-i+1)*H[i];
      else now+=((LL)st.back()-i)*H[i];
      st.push_back(i);
      vr[i]=now;
    }
    LL ans=1LL<<60;
    for(int i=l;i<=r;i++)
    {
      ans=min(ans,vl[i]+vr[i]-H[i]);
      //cout<<i<<' '<<vl[i]<<' '<<vr[i]<<endl;
    }
    C.push_back(ans);
  }
  return C;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 380 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 380 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 302 ms 632 KB Output is correct
11 Correct 900 ms 632 KB Output is correct
12 Correct 298 ms 684 KB Output is correct
13 Correct 886 ms 632 KB Output is correct
14 Correct 130 ms 756 KB Output is correct
15 Correct 151 ms 632 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB Output is correct
2 Correct 3381 ms 1908 KB Output is correct
3 Execution timed out 5587 ms 4868 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB Output is correct
2 Correct 3381 ms 1908 KB Output is correct
3 Execution timed out 5587 ms 4868 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 380 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 302 ms 632 KB Output is correct
11 Correct 900 ms 632 KB Output is correct
12 Correct 298 ms 684 KB Output is correct
13 Correct 886 ms 632 KB Output is correct
14 Correct 130 ms 756 KB Output is correct
15 Correct 151 ms 632 KB Output is correct
16 Correct 2 ms 296 KB Output is correct
17 Correct 3381 ms 1908 KB Output is correct
18 Execution timed out 5587 ms 4868 KB Time limit exceeded
19 Halted 0 ms 0 KB -