oj.uz

Submission #425937

# Submission time Handle Problem Language Result Execution time Memory
425937 2021-06-13T12:27:53 Z MarcoMeijer Meetings (IOI18_meetings) C++14
60 / 100
 712 ms 392260 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<ii> vii;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()

const int MXH = 21;
const int N = (1<<17);

struct T {
  int resl[MXH], resr[MXH];
  int minl[MXH], minr[MXH];
  int maxh;
};
T combine(const T& l, const T& r) {
  if(l.maxh == 0) return r;
  if(r.maxh == 0) return l;
  T res;
  res.maxh = max(l.maxh, r.maxh);
  RE(i,MXH) res.minl[i] = l.minl[i] + r.minl[max(i,l.maxh)];
  RE(i,MXH) res.minr[i] = r.minr[i] + l.minr[max(i,r.maxh)];
  RE(i,MXH) res.resl[i] = res.resr[i] = 1e9;
  RE(i,res.maxh+1) {
    res.resl[i     ] = min(res.resl[i], l.resl[i] + r.minl[l.maxh]);
    res.resr[i     ] = min(res.resr[i], r.resr[i] + l.minr[r.maxh]);
    if(l.maxh == res.maxh && r.maxh != res.maxh)
      res.resr[max(r.maxh,i)] = min(res.resr[max(r.maxh,i)], l.resr[i] + r.minl[i]);
    else
      res.resl[max(l.maxh,i)] = min(res.resl[max(l.maxh,i)], l.resr[i] + r.minl[i]);
    if(l.maxh != res.maxh && r.maxh == res.maxh)
      res.resl[max(l.maxh,i)] = min(res.resl[max(l.maxh,i)], r.resl[i] + l.minr[i]);
    else
      res.resr[max(r.maxh,i)] = min(res.resr[max(r.maxh,i)], r.resl[i] + l.minr[i]);
  }
  return res;
}
T createSingle(int x) {
  T res;
  res.maxh = x;
  RE(i,MXH) res.resl[i]=res.resr[i]=1e9;
  res.resl[x] = res.resr[x] = x;
  RE(i,MXH) res.minl[i]=res.minr[i]=max(x,i);
  return res;
}
T createEmpty() {
  T res;
  res.maxh = 0;
  return res;
}

T seg[N*2];
int h[N];
void buildSeg(int p=1, int l=0, int r=N-1) {
  if(l == r) {
    seg[p] = createSingle(h[l]);
    return;
  }
  int m=(l+r)/2;
  buildSeg(p*2  ,l  ,m);
  buildSeg(p*2+1,m+1,r);
  seg[p] = combine(seg[p*2], seg[p*2+1]);
}
T getSeg(int i, int j, int p=1, int l=0, int r=N-1) {
  if(j < l || i > r) return createEmpty();
  if(i <= l && j >= r) return seg[p];
  int m=(l+r)/2;
  T a = getSeg(i,j,p*2  ,l  ,m);
  T b = getSeg(i,j,p*2+1,m+1,r);
  return combine(a,b);
}

vll minimum_costs(vi H, vi L, vi R) {
  int n = H.size();
  int q = L.size();

  if(n <= 5000 && q <= 5000) {
    vector<vll> costL, costR;
    RE(i,2) (i?costL:costR).assign(n,vll(n,0));
    RE(i,n) {
      ll mx = 0;
      ll res = 0;
      REP(j,i,n) {
        mx = max<ll>(mx,H[j]);
        res += mx;
        costR[j][i] = res;
      }
      mx = res = 0;
      REV(j,0,i+1) {
        mx = max<ll>(mx,H[j]);
        res += mx;
        costL[j][i] = res;
      }
    }

    vll C(q,1e18);
    RE(cq,q) {
      int l=L[cq], r=R[cq];
      REP(i,l,r+1) {
        C[cq] = min(C[cq], costL[l][i] + costR[r][i] - H[i]);
      }
    }
    return C;
  } else {
    RE(i,n) h[i]=H[i];
    buildSeg();
    vll C(q,1e18);
    RE(cq,q) {
      int l=L[cq], r=R[cq];
      T res = getSeg(l,r);
      RE(i,MXH) {
        C[cq] = min<ll>(C[cq], min(res.resr[i], res.resl[i]));
      }
    }
    return C;
  }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 153 ms 141460 KB Output is correct
3 Correct 170 ms 141468 KB Output is correct
4 Correct 163 ms 141460 KB Output is correct
5 Correct 175 ms 141460 KB Output is correct
6 Correct 172 ms 141460 KB Output is correct
7 Correct 150 ms 141456 KB Output is correct
8 Correct 149 ms 141460 KB Output is correct
9 Correct 212 ms 141576 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 153 ms 141460 KB Output is correct
3 Correct 170 ms 141468 KB Output is correct
4 Correct 163 ms 141460 KB Output is correct
5 Correct 175 ms 141460 KB Output is correct
6 Correct 172 ms 141460 KB Output is correct
7 Correct 150 ms 141456 KB Output is correct
8 Correct 149 ms 141460 KB Output is correct
9 Correct 212 ms 141576 KB Output is correct
10 Correct 712 ms 392212 KB Output is correct
11 Correct 659 ms 392260 KB Output is correct
12 Correct 631 ms 392208 KB Output is correct
13 Correct 643 ms 392208 KB Output is correct
14 Correct 616 ms 392208 KB Output is correct
15 Correct 609 ms 392256 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 220 ms 88764 KB Output is correct
3 Correct 556 ms 91036 KB Output is correct
4 Correct 583 ms 91040 KB Output is correct
5 Correct 218 ms 90952 KB Output is correct
6 Correct 466 ms 91040 KB Output is correct
7 Correct 579 ms 91040 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 220 ms 88764 KB Output is correct
3 Correct 556 ms 91036 KB Output is correct
4 Correct 583 ms 91040 KB Output is correct
5 Correct 218 ms 90952 KB Output is correct
6 Correct 466 ms 91040 KB Output is correct
7 Correct 579 ms 91040 KB Output is correct
8 Correct 660 ms 91040 KB Output is correct
9 Correct 638 ms 90952 KB Output is correct
10 Correct 513 ms 91040 KB Output is correct
11 Correct 660 ms 91064 KB Output is correct
12 Correct 666 ms 90980 KB Output is correct
13 Correct 548 ms 90948 KB Output is correct
14 Correct 652 ms 91040 KB Output is correct
15 Correct 602 ms 91040 KB Output is correct
16 Correct 610 ms 91084 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 153 ms 141460 KB Output is correct
3 Correct 170 ms 141468 KB Output is correct
4 Correct 163 ms 141460 KB Output is correct
5 Correct 175 ms 141460 KB Output is correct
6 Correct 172 ms 141460 KB Output is correct
7 Correct 150 ms 141456 KB Output is correct
8 Correct 149 ms 141460 KB Output is correct
9 Correct 212 ms 141576 KB Output is correct
10 Correct 712 ms 392212 KB Output is correct
11 Correct 659 ms 392260 KB Output is correct
12 Correct 631 ms 392208 KB Output is correct
13 Correct 643 ms 392208 KB Output is correct
14 Correct 616 ms 392208 KB Output is correct
15 Correct 609 ms 392256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 220 ms 88764 KB Output is correct
18 Correct 556 ms 91036 KB Output is correct
19 Correct 583 ms 91040 KB Output is correct
20 Correct 218 ms 90952 KB Output is correct
21 Correct 466 ms 91040 KB Output is correct
22 Correct 579 ms 91040 KB Output is correct
23 Correct 660 ms 91040 KB Output is correct
24 Correct 638 ms 90952 KB Output is correct
25 Correct 513 ms 91040 KB Output is correct
26 Correct 660 ms 91064 KB Output is correct
27 Correct 666 ms 90980 KB Output is correct
28 Correct 548 ms 90948 KB Output is correct
29 Correct 652 ms 91040 KB Output is correct
30 Correct 602 ms 91040 KB Output is correct
31 Correct 610 ms 91084 KB Output is correct
32 Runtime error 333 ms 42000 KB Execution killed with signal 11
33 Halted 0 ms 0 KB -