# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
122844 | 2019-06-29T10:58:21 Z | neki | Meetings (IOI18_meetings) | C++14 | 5500 ms | 38180 KB |
#include "meetings.h" #include <bits/stdc++.h> #define maxn 756000 #define loop(i, a, b) for(int i=a;i<b;i++) #define cc(a) cout<< a << endl; using namespace std; std::vector<int> he; struct seg{ int tree[maxn *2]; vector<int> pos[maxn *2]; void build(vector<int> arr){ loop(i, 0, arr.size()){ tree[i+maxn]=arr[i]; pos[i+maxn].push_back(i); } for(int i=maxn-1;i>0;i--){ if(tree[i]<tree[i *2]){tree[i]=tree[i *2];pos[i]=pos[i *2];} else if (tree[i]==tree[i *2]){pos[i].insert(pos[i].end(), pos[i *2].begin(), pos[i *2].end());} if(tree[i]<tree[i *2+1]){tree[i]=tree[i *2+1];pos[i]=pos[i *2+1];} else if (tree[i]==tree[i *2+1]){pos[i].insert(pos[i].end(), pos[i *2+1].begin(), pos[i *2+1].end());} } } vector<int> query(int l, int r){ vector<int> ret; int m=0; for(l+=maxn, r+=maxn;l<r;l>>=1, r>>=1){ if(l&1){ if(m<tree[l]){m=tree[l];ret=pos[l];} else if (m==tree[l]){ret.insert(ret.end(), pos[l].begin(), pos[l].end());} l++; } if(r&1){ r--; if(m<tree[r]){m=tree[r];ret=pos[r];} else if (m==tree[r]){ret.insert(ret.end(), pos[r].begin(), pos[r].end());} } } sort(ret.begin(), ret.end()); return ret; } }; seg re; long long solve(int l, int r){ vector<int> poses=re.query(l, r+1); if(l==r) return he[l]; int m=he[poses[0]]; poses.insert(poses.begin(), l-1);poses.push_back(r+1); long long ans=m*(r-l+1); loop(i, 1, poses.size()){ if(poses[i]==poses[i-1]+1) continue; ans=min(ans, solve(poses[i-1]+1, poses[i]-1)+(long long)m*(r-l+1-((poses[i]-1)-(poses[i-1]+1)+1))); } return ans; } std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) { re.build(H); he=H; vector<long long> ans; loop(i, 0, L.size()){ ans.push_back(solve(L[i], R[i])); } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 45 ms | 35932 KB | Output is correct |
2 | Incorrect | 48 ms | 36184 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 45 ms | 35932 KB | Output is correct |
2 | Incorrect | 48 ms | 36184 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 35900 KB | Output is correct |
2 | Execution timed out | 5529 ms | 38180 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 35900 KB | Output is correct |
2 | Execution timed out | 5529 ms | 38180 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 45 ms | 35932 KB | Output is correct |
2 | Incorrect | 48 ms | 36184 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |