Submission #1026250

#TimeUsernameProblemLanguageResultExecution timeMemory
1026250LalicMeetings (IOI18_meetings)C++17
19 / 100
241 ms202580 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define all(x) x.begin(), x.end() #define allr(x) x.rbegin(), x.rend() #define mp make_pair typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef complex<double> cd; const int MAXN = 1e5+10; const ll LINF = 0x3f3f3f3f3f3f3f3f; struct Node{ int sum, pref, suff, ans; Node(int a=0, int b=0, int c=0, int d=0): sum(a), pref(b), suff(c), ans(d) {} Node operator+ (Node a) const{ Node res; res.sum=this->sum+a.sum; res.pref=max(this->pref, this->sum+a.pref); res.suff=max(this->suff+a.sum, a.suff); res.ans=max({this->ans, a.ans, this->suff+a.pref}); return res; } }; Node tree[4*MAXN]; void upd(int node, int l, int r, int p, int val){ if(r<p || l>p) return; if(l==r){ tree[node]=Node(val, val, val, val); return; } int mid=(l+r)>>1; upd(node*2, l, mid, p, val); upd(node*2+1, mid+1, r, p, val); tree[node]=tree[node*2]+tree[node*2+1]; } Node query(int node, int l, int r, int p, int q){ if(r<p || l>q) return Node(-1e8, -1e8, -1e8, -1e8); if(l>=p && r<=q) return tree[node]; int mid=(l+r)>>1; return query(node*2, l, mid, p, q)+query(node*2+1, mid+1, r, p, q); } vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) { int q=(int)L.size(), n=(int)H.size(); if(n<=5000){ vector<ll> ans(q); vector<vector<ll>> res(n, vector<ll>(n)); for(int i=0;i<n;i++){ res[i][i]=H[i]; int curr=H[i]; for(int j=i+1;j<n;j++){ curr=max(curr, H[j]); res[i][j]=res[i][j-1]+curr; } curr=H[i]; for(int j=i-1;j>=0;j--){ curr=max(curr, H[j]); res[i][j]=res[i][j+1]+curr; } } for(int i=0;i<q;i++){ ll best=LINF; for(int j=L[i];j<=R[i];j++) best=min(best, res[j][L[i]]+res[j][R[i]]-H[j]); ans[i]=best; } return ans; } for(int i=0;i<n;i++){ if(H[i]==1) upd(1, 0, n-1, i, 1); else upd(1, 0, n-1, i, -1e8); } vector<ll> ans(q); for(int i=0;i<q;i++){ Node interv=query(1, 0, n-1, L[i], R[i]); //~ cout << interv.ans << "\n"; int res=2*(R[i]-L[i]+1); if(interv.ans>=0) res-=interv.ans; ans[i]=res; } return ans; }
#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...