oj.uz

Submission #915815

# Submission time Handle Problem Language Result Execution time Memory
915815 2024-01-24T18:23:23 Z biank Meetings (IOI18_meetings) C++14
19 / 100
 415 ms 758496 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 INF = 1e18;
const int MAXN = 1e5;
const int MAXH = 21;

struct Node {
    ll pref[MAXH], suff[MAXH], cost[MAXH][MAXH];
    int maxH;
    Node() {
        forn(i,MAXH) {
            pref[i]=suff[i]=INF;
            forn(j,MAXH) cost[i][j]=INF;
        }
        maxH=0;
    }
    Node(int val) {
        forn(i,MAXH) {
            pref[i]=suff[i]=INF;
            forn(j,MAXH) cost[i][j]=INF;
        }
        cost[val][val]=maxH=val;
        forn(i,MAXH) pref[i]=suff[i]=max(i,val);
    }
};

Node op(Node left, Node right) {
    Node res;
    forn(i,MAXH) forn(j,MAXH) {
        ll &curr = res.cost[i][max(j,right.maxH)];
        curr = min(curr, left.cost[i][j] + right.pref[j]);
    }
    forn(i,MAXH) forn(j,MAXH) {
        ll &curr = res.cost[max(i,left.maxH)][j];
        curr = min(curr, left.suff[i] + right.cost[i][j]);
    }
    forn(i,MAXH) {
        res.suff[i] = min(res.suff[i], left.pref[max(i,right.maxH)] + right.pref[i]);
        res.pref[i] = min(res.pref[i], left.suff[i] + right.suff[max(i,left.maxH)]);
    }
    res.maxH = max(left.maxH, right.maxH);
    return res;
}

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 = op(ansL, st[l++]);
        if(r&1) ansR = op(st[--r], ansR);
    }
    Node ans = op(ansL, ansR);
    ll res=INF;
    forn(i,MAXH) forn(j,MAXH) {
        res=min(res,ans.cost[i][j]);
    }
    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]=op(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,INF);
    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 274 ms 758096 KB Output is correct
2 Correct 296 ms 758172 KB Output is correct
3 Correct 307 ms 758228 KB Output is correct
4 Correct 307 ms 758040 KB Output is correct
5 Correct 307 ms 758232 KB Output is correct
6 Correct 295 ms 758096 KB Output is correct
7 Correct 296 ms 758100 KB Output is correct
8 Correct 299 ms 758140 KB Output is correct
9 Correct 306 ms 758216 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 758096 KB Output is correct
2 Correct 296 ms 758172 KB Output is correct
3 Correct 307 ms 758228 KB Output is correct
4 Correct 307 ms 758040 KB Output is correct
5 Correct 307 ms 758232 KB Output is correct
6 Correct 295 ms 758096 KB Output is correct
7 Correct 296 ms 758100 KB Output is correct
8 Correct 299 ms 758140 KB Output is correct
9 Correct 306 ms 758216 KB Output is correct
10 Correct 399 ms 758272 KB Output is correct
11 Correct 400 ms 758356 KB Output is correct
12 Correct 392 ms 758496 KB Output is correct
13 Correct 395 ms 758456 KB Output is correct
14 Correct 394 ms 758472 KB Output is correct
15 Correct 415 ms 758336 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 24.0

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

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 758096 KB Output is correct
2 Correct 296 ms 758172 KB Output is correct
3 Correct 307 ms 758228 KB Output is correct
4 Correct 307 ms 758040 KB Output is correct
5 Correct 307 ms 758232 KB Output is correct
6 Correct 295 ms 758096 KB Output is correct
7 Correct 296 ms 758100 KB Output is correct
8 Correct 299 ms 758140 KB Output is correct
9 Correct 306 ms 758216 KB Output is correct
10 Correct 399 ms 758272 KB Output is correct
11 Correct 400 ms 758356 KB Output is correct
12 Correct 392 ms 758496 KB Output is correct
13 Correct 395 ms 758456 KB Output is correct
14 Correct 394 ms 758472 KB Output is correct
15 Correct 415 ms 758336 KB Output is correct
16 Incorrect 265 ms 758272 KB Output isn't correct
17 Halted 0 ms 0 KB -