oj.uz

Submission #139323

# Submission time Handle Problem Language Result Execution time Memory
139323 2019-07-31T14:48:12 Z Meloric Meetings (IOI18_meetings) C++14
36 / 100
 997 ms 9772 KB 
#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define X first
#define Y second

using namespace std;

ll ez(int l, int r, vector<int>& H){
    vector<ll> le, ri, st, am;
    le.assign(H.size(), 0);
    ri.assign(H.size(), 0);
    ll cur = 0;
    for(int i = l; i<=r; i++){
        ll tmp = 1;
        while(st.size()>0 && st.back() <= H[i]){
            tmp+=am.back();
            cur-=am.back()*st.back();
            st.pop_back();
            am.pop_back();
        }
        cur+=tmp*H[i];
        le[i] = cur;
        st.pb((ll)H[i]);
        am.pb(tmp);
    }
    cur = 0;
    st.clear(); am.clear();
    for(int i = r; i>=l; i--){
        ll tmp = 1;
        while(st.size()>0 && st.back() <= H[i]){
            tmp+=am.back();
            cur-=am.back()*st.back();
            st.pop_back();
            am.pop_back();
        }
        cur+=tmp*H[i];
        ri[i] = cur;
        st.pb((ll)H[i]);
        am.pb(tmp);
    }
    ll ret = 1e15;
    for(int i = l; i<=r; i++){
        ret = min(ret, le[i]+ri[i]-H[i]);
    }
    return ret;
}
struct node{
    int prf, suf, sum, flag;
};
vector<node> seg;
node conq(node& a, node& b){
    node c;
    c.flag = a.flag & b.flag;
    if(a.flag){
        c.prf = a.sum + b.prf;
    }else{
        c.prf = a.prf;
    }
    if(b.flag){
        c.suf = a.suf + b.sum;
    }else{
        c.suf = b.suf;
    }
    c.sum = max(a.sum, b.sum);
    c.sum = max(c.sum, a.suf + b. prf);
    return c;
}
void build(int v, int tl, int tr, vector<int>& H){
    if(tl ==  tr){
        if(H[tl] == 1){
            seg[v] = {1, 1, 1, 1};
        }
        return;
    }
    int tm = (tl+tr)/2;
    build(v*2, tl, tm, H);
    build(v*2+1, tm+1, tr, H);
    seg[v] = conq(seg[2*v], seg[2*v+1]);
}
node qer(int v, int tl, int tr, int l, int r){
    if(tl > r || tr < l)return {-1, -1, -1, -1};
    if(tl >= l && tr <= r)return seg[v];
    int tm = (tl+tr)/2;
    node le = qer(v*2, tl, tm, l, r);
    node ri = qer(v*2+1, tm+1, tr, l, r);
    if(le.flag == -1)return ri;
    if(ri.flag == -1)return le;
    return conq(le, ri);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,
                                     vector<int> R) {
  int Q = L.size();
  int N = H.size();
  vector<ll> C(Q);
  if(N <= 5005 && Q <= 5005){
    for (int j = 0; j < Q; ++j) {
        C[j] = ez(L[j], R[j], H);
    }
    return C;
  }
  seg.assign(4*N, {0, 0, 0, 0});
  build(1, 0, N-1, H);
  for (int j = 0; j < Q; ++j) {
    int sum =  qer(1, 0, N-1, L[j], R[j]).sum;
    sum+=(R[j]-L[j]+1-sum)*2;
    C[j] = sum;
  }
  return C;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 4 ms 316 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 420 KB Output is correct
8 Correct 2 ms 376 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 348 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 4 ms 316 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 420 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 350 ms 596 KB Output is correct
11 Correct 997 ms 600 KB Output is correct
12 Correct 344 ms 600 KB Output is correct
13 Correct 995 ms 600 KB Output is correct
14 Correct 217 ms 592 KB Output is correct
15 Correct 254 ms 604 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 47 ms 2092 KB Output is correct
3 Correct 146 ms 9740 KB Output is correct
4 Correct 146 ms 9772 KB Output is correct
5 Correct 104 ms 9752 KB Output is correct
6 Correct 133 ms 9768 KB Output is correct
7 Correct 142 ms 9720 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 47 ms 2092 KB Output is correct
3 Correct 146 ms 9740 KB Output is correct
4 Correct 146 ms 9772 KB Output is correct
5 Correct 104 ms 9752 KB Output is correct
6 Correct 133 ms 9768 KB Output is correct
7 Correct 142 ms 9720 KB Output is correct
8 Incorrect 144 ms 9744 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 4 ms 316 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 420 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 350 ms 596 KB Output is correct
11 Correct 997 ms 600 KB Output is correct
12 Correct 344 ms 600 KB Output is correct
13 Correct 995 ms 600 KB Output is correct
14 Correct 217 ms 592 KB Output is correct
15 Correct 254 ms 604 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 47 ms 2092 KB Output is correct
18 Correct 146 ms 9740 KB Output is correct
19 Correct 146 ms 9772 KB Output is correct
20 Correct 104 ms 9752 KB Output is correct
21 Correct 133 ms 9768 KB Output is correct
22 Correct 142 ms 9720 KB Output is correct
23 Incorrect 144 ms 9744 KB Output isn't correct
24 Halted 0 ms 0 KB -