oj.uz

Submission #915811

# Submission time Handle Problem Language Result Execution time Memory
915811 2024-01-24T18:01:37 Z biank Meetings (IOI18_meetings) C++14
19 / 100
 270 ms 379740 KB 
//#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define SIZE(x) int(x.size())
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
const ll INFLL = 1e18;
const int INF = 1e9;
const int MAXN = 1e5;
const int MAXH = 21;

struct Node {
    int pref[MAXH], suff[MAXH], cost[MAXH][MAXH], maxH;
    Node() {
        forn(i,MAXH) {
            pref[i]=suff[i]=INF;
            forn(j,MAXH) cost[i][j]=INF;
        }
        maxH=0;
    }
    Node(int val) : Node() {
        cost[val][val] = maxH = val;
        forn(i,MAXH) pref[i] = suff[i] = max(i,val);
    }
    Node(Node left, Node right) : Node() {
        maxH = max(left.maxH, right.maxH);
        forn(i,MAXH) {
            int &curr = cost[i][maxH];
            curr = min(curr, left.cost[i][left.maxH] + right.pref[left.maxH]);
        }
        forn(i,MAXH) {
            int &curr = cost[left.maxH][max(i,right.maxH)];
            curr = min(curr, left.cost[left.maxH][i] + right.pref[i]);
        }
        forn(i,MAXH) {
            int &curr = cost[max(i,left.maxH)][right.maxH];
            curr = min(curr, left.suff[i] + right.cost[i][right.maxH]);
        }
        forn(i,MAXH) {
            int &curr = cost[maxH][i];
            curr = min(curr, left.suff[right.maxH] + right.cost[right.maxH][i]);
        }
        forn(i,MAXH) {
            pref[i] = min(pref[i], left.pref[i] + right.pref[max(i,left.maxH)]);
            suff[i] = min(suff[i], left.suff[max(i,right.maxH)] + right.suff[i]);
        }
    }
};

Node st[2*MAXN];
int n;

ll query(int l, int r) {
    Node ansL, ansR;
    for(l+=n, r+=n; l<r; l/=2, r/=2) {
        if(l&1) ansL=Node(ansL,st[l++]);
        if(r&1) ansR=Node(st[--r],ansR);
    }
    Node ans=Node(ansL, ansR);
    ll res=INFLL;
    forn(i,MAXH) res=min({res,(ll)ans.cost[ans.maxH][i],(ll)ans.cost[i][ans.maxH]});
    return res;
}

vll subtask4(vi h, vi l, vi r) { //no anda
    n=SIZE(h);
    forn(i,n) st[i+n]=Node(h[i]);
    dforn(i,n) st[i]=Node(st[2*i],st[2*i+1]);
    int q=SIZE(l);
    vll ans(q);
    forn(i,q) ans[i]=query(l[i],r[i]+1);
    return ans;
}

vll minimum_costs(vi h, vi l, vi r) {
    int q=SIZE(l), n=SIZE(h);
    bool s4=q<=MAXN&&n<=MAXN;
    forn(i,n) s4&=h[i]<MAXH;
    if(s4) return subtask4(h,l,r);
    vll ans(q,INFLL);
    forn(i,n) {
        vi c(n);
        c[i]=h[i];
        dforn(j,i) c[j]=max(c[j+1],h[j]);
        forsn(j,i+1,n) c[j]=max(c[j-1],h[j]);
        vll p(n+1);
        p[0]=0;
        forn(j,n) p[j+1]=p[j]+c[j];
        forn(j,q) ans[j]=min(ans[j],p[r[j]+1]-p[l[j]]);
    }
    return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 379044 KB Output is correct
2 Correct 178 ms 379340 KB Output is correct
3 Correct 171 ms 379096 KB Output is correct
4 Correct 177 ms 379232 KB Output is correct
5 Correct 182 ms 379404 KB Output is correct
6 Correct 178 ms 379332 KB Output is correct
7 Correct 172 ms 379204 KB Output is correct
8 Correct 174 ms 379224 KB Output is correct
9 Correct 168 ms 379220 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 379044 KB Output is correct
2 Correct 178 ms 379340 KB Output is correct
3 Correct 171 ms 379096 KB Output is correct
4 Correct 177 ms 379232 KB Output is correct
5 Correct 182 ms 379404 KB Output is correct
6 Correct 178 ms 379332 KB Output is correct
7 Correct 172 ms 379204 KB Output is correct
8 Correct 174 ms 379224 KB Output is correct
9 Correct 168 ms 379220 KB Output is correct
10 Correct 263 ms 379488 KB Output is correct
11 Correct 270 ms 379740 KB Output is correct
12 Correct 263 ms 379472 KB Output is correct
13 Correct 261 ms 379472 KB Output is correct
14 Correct 262 ms 379472 KB Output is correct
15 Correct 263 ms 379476 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 379220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 379220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 379044 KB Output is correct
2 Correct 178 ms 379340 KB Output is correct
3 Correct 171 ms 379096 KB Output is correct
4 Correct 177 ms 379232 KB Output is correct
5 Correct 182 ms 379404 KB Output is correct
6 Correct 178 ms 379332 KB Output is correct
7 Correct 172 ms 379204 KB Output is correct
8 Correct 174 ms 379224 KB Output is correct
9 Correct 168 ms 379220 KB Output is correct
10 Correct 263 ms 379488 KB Output is correct
11 Correct 270 ms 379740 KB Output is correct
12 Correct 263 ms 379472 KB Output is correct
13 Correct 261 ms 379472 KB Output is correct
14 Correct 262 ms 379472 KB Output is correct
15 Correct 263 ms 379476 KB Output is correct
16 Incorrect 139 ms 379220 KB Output isn't correct
17 Halted 0 ms 0 KB -