Submission #1048954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048954		Alihan_8	Meetings (IOI18_meetings)	C++17	0 / 100	1337 ms	786432 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const i64 inf = 1e15;

const int N = 1e5 + 1;

int n;

struct SegTree{
	struct Info{
		i64 dp[21][21];
		
		vector <ar<int,2>> ls, rs;
		
		Info(){
			for ( int i = 0; i <= 20; i++ ){
				for ( int j = 0; j <= 20; j++ ){
					dp[i][j] = inf;
				}
			}
 			
			ls.pb({0, 0});
			rs.pb({0, 0});
		}
	};
	
	vector <Info> T;
	
	void modify(int n){ T.resize(n * 4 + 5); }
		
	void merge(Info &rt, const Info &lf, const Info &rg){
		rt = Info();
		
		rt.ls = lf.ls;
		for ( auto &[h, v]: rg.ls ){
			if ( rt.ls.back()[0] < h ){
				rt.ls.pb({h, v});
			} else rt.ls.back()[1] += v;
		}
		
		rt.rs = rg.rs;
		for ( auto &[h, v]: lf.rs ){
			if ( rt.rs.back()[0] < h ){
				rt.rs.pb({h, v});
			} else rt.rs.back()[1] += v;
		}
		
		for ( int x = 0; x <= 20; x++ ){
			i64 cnt = 0, pf = 0;
			
			for ( auto &[h, v]: rg.ls ){
				cnt += h * 1LL * v;
			}
			
			int j = 0;
			
			for ( int y = 0; y <= 20; y++ ){
				int r = max(y, rg.ls.back()[0]);
				
				cnt += pf;
				
				while ( j < (int)rg.ls.size() && rg.ls[j][0] <= y ){
					auto &[h, v] = rg.ls[j++];
					
					cnt += (y - h) * 1LL * v;
					pf += v;
				}
				
				chmin(rt.dp[x][r], lf.dp[x][y] + cnt);
			}
		}
		
		for ( int y = 0; y <= 20; y++ ){
			i64 cnt = 0, pf = 0;
			
			for ( auto &[h, v]: lf.rs ){
				cnt += h * 1LL * v;
			}
			
			int j = 0;
			
			for ( int x = 0; x <= 20; x++ ){
				int l = max(x, lf.rs.back()[0]);
				
				cnt += pf;
				
				while ( j < (int)lf.rs.size() && lf.rs[j][0] <= x ){
					auto &[h, v] = lf.rs[j++];
					
					cnt += (x - h) * 1LL * v;
					pf += v;
				}
				
				chmin(rt.dp[l][y], rg.dp[x][y] + cnt);
			}
		}
	}
	
	void upd(int v, int l, int r, int p, int x){
		if ( l == r ){
			T[v].dp[x][x] = x;
			T[v].ls.pb({x, 1});
			T[v].rs.pb({x, 1});
			
			return;
		}
		
		int m = (l + r) / 2;
		
		if ( p <= m ) upd(v * 2, l, m, p, x);
		else  upd(v * 2 + 1, m + 1, r, p, x);
		
		merge(T[v], T[v * 2], T[v * 2 + 1]);
	}
	
	void upd(int p, int x){ upd(1, 0, n - 1, p, x); }	
	
	Info get(int v, int l, int r, int tl, int tr){
		Info ret;
		
		if ( l > tr or r < tl ) return ret;
		
		if ( tl <= l && tr >= r ){
			return T[v];
		}
		
		int m = (l + r) / 2;
		
		if ( m < tl ) return get(v * 2 + 1, m + 1, r, tl, tr);
		
		if ( m + 1 > tr ) return get(v * 2, l, m, tl, tr);
		
		merge(ret, get(v * 2, l, m, tl, tr), get(v * 2 + 1, m + 1, r, tl, tr));
		
		return ret;
	} 
	
	i64 qry(int l, int r){
		Info q = get(1, 0, n - 1, l, r);
		
		i64 opt = inf;
		
		for ( int x = 0; x <= 20; x++ ){
			for ( int y = 0; y <= 20; y++ ){
				chmin(opt, q.dp[x][y]);
			}
		}
		
		return opt;
	};
} seg;

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	int q = L.size(); n = H.size(); 
	
	// subtask #4
	
	seg.modify(n);
	
	for ( int i = 0; i < n; i++ ){
		seg.upd(i, H[i]);
	}
	
	vector <i64> ans(q);
	
	for ( int i = 0; i < q; i++ ){
		ans[i] = seg.qry(L[i], R[i]);
	}
	
	return ans;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40