Submission #111960

#TimeUsernameProblemLanguageResultExecution timeMemory
111960mechfrog88Meetings (IOI18_meetings)C++14
19 / 100
708 ms196452 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; ll k; vector<ll> s; vector<ll> diff; void build(ll id = 1, ll l=0,ll r = k){ if (r - l < 2){ s[id] = diff[l]; return; } ll mid = (l+r)/2; build(id*2,l,mid); build(id*2+1,mid,r); s[id] = min(s[id*2],s[id*2+1]); } ll query(ll x,ll y,ll id = 1,ll l =0,ll r = k){ if (y <= l || x >= r) return LLONG_MAX; if (x <= l && r <= y){ return s[id]; } ll mid = (l+r)/2; return min(query(x,y,id*2,l,mid),query(x,y,id*2+1,mid,r)); } vector<ll> minimum_costs(vector<int> h,vector<int> l,vector<int> r) { int n = l.size(); ll a = h.size(); vector<ll> c(n); bool sub3 = true; for (int z=0;z<a;z++){ if (h[z] > 2){ sub3 = false; break; } } if (sub3){ vector<ll> high; for (int z=0;z<a;z++){ if (h[z] == 2) { high.push_back(z); if (high.size() >= 2){ ll temp = *high.rbegin()-(*(high.rbegin()+1))-1; if (temp == 0) temp = LLONG_MAX; diff.push_back(temp); } } } k = diff.size(); if (k != 0){ s.resize(k*4,LLONG_MAX); build(); } for (int z=0;z<n;z++){ ll left = l[z]; ll right = r[z]; if (left == right){ c[z] = h[z]; continue; } auto it = lower_bound(high.begin(),high.end(),left); auto ita = lower_bound(high.begin(),high.end(),right); c[z] = LLONG_MAX; if (it == ita){ c[z] = (right-left+1); if (*it == left) { c[z]--; c[z] += 2; } if (*ita == right) { c[z]--; c[z] += 2; } continue; } ll x = *it; ll y; if (*ita == right){ y = *(ita); } else { y = *(ita-1); } c[z] = min((right-y)+2*(y-left+1),(x-left)+2*(right-x+1)); ll r; if (*ita != right){ r = query(it-high.begin(),ita-high.begin()-1); } else { r = query(it-high.begin(),ita-high.begin()); } if (r != LLONG_MAX) c[z] = min(c[z],r+2*(right-left+1-r)); } return c; } else{ vector <vector<ll>> d(a,vector<ll>(a,0)); for (int z=0;z<a;z++){ ll maxi = h[z]; d[z][z] = h[z]; for (int x=z+1;x<a;x++){ maxi = max(maxi,ll(h[x])); d[z][x] = d[z][x-1] + maxi; } maxi = h[z]; for (int x=z-1;x>-1;x--){ maxi = max(maxi,ll(h[x])); d[z][x] = d[z][x+1] + maxi; } } for (int z=0;z<n;z++){ ll left = l[z]; ll right = r[z]; c[z] = LLONG_MAX; for (int x=left;x<=right;x++){ c[z] = min(c[z],d[x][right]+d[x][left]-ll(h[x])); } } return c; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...