# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
915830 |
2024-01-24T18:45:14 Z |
biank |
Meetings (IOI18_meetings) |
C++14 |
|
555 ms |
768644 KB |
#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 int INF = 1e9;
const int MAXN = 1e5;
const int MAXH = 21;
struct Node {
int pref[MAXH], suff[MAXH];
int cost[MAXH][MAXH];
int maxH;
Node() {
forn(i,MAXH) {
pref[i]=suff[i]=INF;
forn(j,MAXH) cost[i][j]=INF;
}
maxH=0;
}
};
Node init(int v) {
Node u;
u.cost[v][v]=u.maxH=v;
forn(i,MAXH) u.pref[i]=u.suff[i]=max(i,v);
return u;
}
void mini(int &curr, int v) {
curr=min(curr,v);
}
Node op(Node left, Node right) {
Node u;
forn(i,MAXH) {
int j=left.maxH;
mini(u.cost[i][max(j,right.maxH)], left.cost[i][j] + right.pref[j]);
}
forn(i,MAXH) {
int j=right.maxH;
mini(u.cost[max(i,left.maxH)][j], left.suff[i] + right.cost[i][j]);
}
forn(j,MAXH) {
int i=left.maxH;
mini(u.cost[i][max(j,right.maxH)], left.cost[i][j] + right.pref[j]);
}
forn(j,MAXH) {
int i=right.maxH;
mini(u.cost[max(i,left.maxH)][j], left.suff[i] + right.cost[i][j]);
}
forn(i,MAXH) {
mini(u.suff[i], left.suff[max(i,right.maxH)] + right.suff[i]);
mini(u.pref[i], left.pref[i] + right.pref[max(i,left.maxH)]);
}
u.maxH = max(left.maxH, right.maxH);
return u;
}
Node st[2*MAXN];
int n;
int 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 res=op(ansL,ansR);
int ans=INF;
forn(i,MAXH) {
int j=res.maxH;
mini(ans,res.cost[i][j]);
mini(ans,res.cost[j][i]);
}
return ans;
}
vll minimum_costs(vi h, vi l, vi r) {
n=SIZE(h);
forn(i,n) st[i+n]=init(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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
555 ms |
768644 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
555 ms |
768644 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
158 ms |
379280 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
158 ms |
379280 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
555 ms |
768644 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |