oj.uz

Submission #915812

# Submission time Handle Problem Language Result Execution time Memory
915812 2024-01-24T18:14:20 Z biank Meetings (IOI18_meetings) C++14
19 / 100
 449 ms 758472 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) : Node() {
        cost[val][val]=maxH=val;
        forn(i,MAXH) pref[i]=suff[i]=max(i,val);
    }
    Node(Node left, Node right) : Node() {
        forn(i,MAXH) forn(j,MAXH) {
            ll &curr = cost[i][max(j,right.maxH)];
            curr = min(curr, left.cost[i][j] + right.pref[j]);
        }
        forn(i,MAXH) forn(j,MAXH) {
            ll &curr = cost[max(i,left.maxH)][j];
            curr = min(curr, left.suff[i] + right.cost[i][j]);
        }
        maxH = max(left.maxH, right.maxH);
        forn(i,MAXH) {
            suff[i] = min(suff[i], left.pref[max(i,right.maxH)] + right.pref[i]);
            pref[i] = min(pref[i], left.suff[i] + right.suff[max(i,left.maxH)]);
        }
    }
};

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=INF;
    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,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 330 ms 757952 KB Output is correct
2 Correct 307 ms 757992 KB Output is correct
3 Correct 298 ms 758096 KB Output is correct
4 Correct 304 ms 758016 KB Output is correct
5 Correct 298 ms 758200 KB Output is correct
6 Correct 304 ms 758100 KB Output is correct
7 Correct 298 ms 758104 KB Output is correct
8 Correct 304 ms 758140 KB Output is correct
9 Correct 346 ms 758100 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 757952 KB Output is correct
2 Correct 307 ms 757992 KB Output is correct
3 Correct 298 ms 758096 KB Output is correct
4 Correct 304 ms 758016 KB Output is correct
5 Correct 298 ms 758200 KB Output is correct
6 Correct 304 ms 758100 KB Output is correct
7 Correct 298 ms 758104 KB Output is correct
8 Correct 304 ms 758140 KB Output is correct
9 Correct 346 ms 758100 KB Output is correct
10 Correct 392 ms 758380 KB Output is correct
11 Correct 390 ms 758352 KB Output is correct
12 Correct 399 ms 758472 KB Output is correct
13 Correct 449 ms 758468 KB Output is correct
14 Correct 398 ms 758464 KB Output is correct
15 Correct 399 ms 758352 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 24.0

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

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 757952 KB Output is correct
2 Correct 307 ms 757992 KB Output is correct
3 Correct 298 ms 758096 KB Output is correct
4 Correct 304 ms 758016 KB Output is correct
5 Correct 298 ms 758200 KB Output is correct
6 Correct 304 ms 758100 KB Output is correct
7 Correct 298 ms 758104 KB Output is correct
8 Correct 304 ms 758140 KB Output is correct
9 Correct 346 ms 758100 KB Output is correct
10 Correct 392 ms 758380 KB Output is correct
11 Correct 390 ms 758352 KB Output is correct
12 Correct 399 ms 758472 KB Output is correct
13 Correct 449 ms 758468 KB Output is correct
14 Correct 398 ms 758464 KB Output is correct
15 Correct 399 ms 758352 KB Output is correct
16 Incorrect 264 ms 758096 KB Output isn't correct
17 Halted 0 ms 0 KB -