oj.uz

Submission #915809

# Submission time Handle Problem Language Result Execution time Memory
915809 2024-01-24T17:59:55 Z biank Meetings (IOI18_meetings) C++14
19 / 100
 275 ms 379848 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) {
        cost[val][val] = maxH = val;
        forn(i,MAXH) pref[i] = suff[i] = max(i,val);
    }
    Node(Node left, Node right) {
        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) {
    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 152 ms 379220 KB Output is correct
2 Correct 181 ms 379216 KB Output is correct
3 Correct 190 ms 379220 KB Output is correct
4 Correct 184 ms 379220 KB Output is correct
5 Correct 179 ms 379312 KB Output is correct
6 Correct 180 ms 379120 KB Output is correct
7 Correct 175 ms 379368 KB Output is correct
8 Correct 185 ms 379224 KB Output is correct
9 Correct 174 ms 379216 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 379220 KB Output is correct
2 Correct 181 ms 379216 KB Output is correct
3 Correct 190 ms 379220 KB Output is correct
4 Correct 184 ms 379220 KB Output is correct
5 Correct 179 ms 379312 KB Output is correct
6 Correct 180 ms 379120 KB Output is correct
7 Correct 175 ms 379368 KB Output is correct
8 Correct 185 ms 379224 KB Output is correct
9 Correct 174 ms 379216 KB Output is correct
10 Correct 273 ms 379724 KB Output is correct
11 Correct 269 ms 379472 KB Output is correct
12 Correct 270 ms 379848 KB Output is correct
13 Correct 264 ms 379496 KB Output is correct
14 Correct 275 ms 379604 KB Output is correct
15 Correct 269 ms 379476 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 143 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 143 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 152 ms 379220 KB Output is correct
2 Correct 181 ms 379216 KB Output is correct
3 Correct 190 ms 379220 KB Output is correct
4 Correct 184 ms 379220 KB Output is correct
5 Correct 179 ms 379312 KB Output is correct
6 Correct 180 ms 379120 KB Output is correct
7 Correct 175 ms 379368 KB Output is correct
8 Correct 185 ms 379224 KB Output is correct
9 Correct 174 ms 379216 KB Output is correct
10 Correct 273 ms 379724 KB Output is correct
11 Correct 269 ms 379472 KB Output is correct
12 Correct 270 ms 379848 KB Output is correct
13 Correct 264 ms 379496 KB Output is correct
14 Correct 275 ms 379604 KB Output is correct
15 Correct 269 ms 379476 KB Output is correct
16 Incorrect 143 ms 379220 KB Output isn't correct
17 Halted 0 ms 0 KB -