제출 #431383

#제출 시각아이디문제언어결과실행 시간메모리
431383AmineWeslati모임들 (IOI18_meetings)C++14
17 / 100
169 ms12084 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int>vi; #define pb push_back #define all(x) begin(x),end(x) #define sz(v) (int)v.size() #define FOR(i,a,b) for(int i=a; i<b; i++) #define ROF(i,a,b) for(int i=b-1; i>=a; i--) //------------------------------------------ const int MX=1e5+10; const ll INF=1e18; void ckmin(ll &x, ll y){x=min(x,y);} void ckmax(int &x, int y){x=max(x,y);} int N,Q; vi a; struct node{ int mx,al,lft,rgt; }; vector<node>t(MX*4); node combine(node a, node b){ node c; c.lft=a.lft; if(a.al) c.lft=a.mx+b.lft; c.rgt=b.rgt; if(b.al) c.rgt=b.mx+a.rgt; c.mx=max(max(a.mx,b.mx),a.rgt+b.lft); c.al=a.al&b.al; return c; } void build(int pos=1, int tl=0, int tr=N-1){ if(tl==tr){ int x=(a[tl]==1); t[pos]={x,x,x,x}; return; } int tm=(tl+tr)/2; build(pos*2,tl,tm); build(pos*2+1,tm+1,tr); t[pos]=combine(t[pos*2],t[pos*2+1]); } node get(int l, int r, int pos=1, int tl=0, int tr=N-1){ if(l>r) return node{0,0,0,0}; if(l==tl && r==tr){ return t[pos]; } int tm=(tl+tr)/2; return combine(get(l,min(r,tm),pos*2,tl,tm), get(max(l,tm+1),r,pos*2+1,tm+1,tr)); } vector<ll> minimum_costs(vi H, vi L, vi R){ N=sz(H),Q=sz(L); a.assign(all(H)); build(); vector<ll>res(Q); FOR(idx,0,Q){ int len=get(L[idx],R[idx]).mx; res[idx]=len+(R[idx]-L[idx]+1-len)*2; } return res; } /* 4 2 2 4 3 5 0 2 1 3 */ /* 10 2 2 1 1 1 2 1 1 2 2 2 0 9 0 4 */
#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...