Submission #1225142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225142		thelegendary08	Meetings (IOI18_meetings)	C++20	4 / 100	5585 ms	3108 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
struct segtree{ //range set range sum
	vi tree, lz, tl, tr; int n;
	segtree(int x){
		n = x; tree.resize(4 * n + 5); lz.resize(4 * n + 5); tl.resize(4*n+5); tr.resize(4 * n + 5);
		build(1, 0, n-1);
		f0r(i, 4 * n + 5){
			lz[i] = -1;
		}
	}
	void build(int v, int l, int r){
		tl[v] = l; tr[v] = r;
		if(l == r)return;
		int mid = (l + r) / 2;
		build(v * 2, l, mid);
		build(v*2+1, mid + 1, r);
	}
	void pull(int v){
		tree[v] = tree[v*2] + tree[v*2+1];
	}
	int sz(int v){
		return tr[v] - tl[v] + 1;
	}
	void sett(int v, int x){
		tree[v] = sz(v) * x; 
		lz[v] = x;
	}
	void push(int v){
		if(lz[v] != -1){
			sett(v*2, lz[v]);
			sett(v*2+1, lz[v]);
			lz[v] = -1;
		}
	}
	void rs(int v, int l, int r, int x){
		if(tl[v] > r || tr[v] < l)return;
		if(tl[v] >= l && tr[v] <= r)sett(v, x);
		else{
			push(v);
			rs(v*2, l, r, x);
			rs(v*2+1, l, r, x);
			pull(v);
		}
	}
	int sq(int v, int l, int r){
		if(tl[v] > r || tr[v] < l)return 0;
		if(tl[v] >= l && tr[v] <= r)return tree[v];
		else{
			push(v);
			return sq(v*2, l, r) + sq(v*2+1, l, r);
		}
	}
};
std::vector<long long> minimum_costs(std::vector<signed> H, std::vector<signed> L,
                                     std::vector<signed> R) {
	signed Q = L.size();
	vi ans(Q);
	int ct = 0;
	f0r(tt, Q){
		vi v;
		FOR(i, L[tt], R[tt]+1){
			v.pb(H[i]);
		}
		
		int n = R[tt] - L[tt] + 1;
		vpii w;
		f0r(i, n){
			w.pb(mp(v[i], i));
		}
		sort(rall(w));
		
		segtree t = segtree(n);
		int curans = 4e18;
		
		vi l(n); vi r(n);
		stack<pii>s;
		for(int i = n-1; i>=0; i--){
			while(!s.empty() && s.top().first <= v[i]){
				s.pop();
			}
			if(s.empty())r[i] = n;
			else{
				r[i] = s.top().second;
			}
			s.push(mp(v[i], i));
		}
		s = stack<pii>();
		f0r(i,n){
			while(!s.empty() && s.top().first <= v[i]){
				s.pop();
			}
			if(s.empty())l[i] = -1;
			else{
				l[i] = s.top().second;
			}
			s.push(mp(v[i], i));
		}
		
		// vout(l); vout(r);
		
		vpii sl;
		vpii sr;
		int mx = 0;
		f0r(i,n){
			if(v[i] > mx){
				mx = v[i]; 
				sr.pb(mp(v[i], i));
			}
		}
		
		reverse(all(sr));
		for(int i = sr.size() - 1; i>=0; i--){
			t.rs(1, sr[i].second, r[sr[i].second] - 1, sr[i].first);
		}
		
		/*
		f0r(i,n){
			cout<<t.sq(1, i, i)<<' ';
		}
		cout<<'\n';
		*/
		
		f0r(i, n){
			if(i != 0){
				vpii tmp;
				int cur = i;
				int bd = n; 
				if(sr.size() >= 2){
					bd = sr[sr.size() - 2].second;
				}
				while(cur != bd){
					tmp.pb(mp(v[cur], cur));
					t.rs(1, cur, r[cur] - 1, v[cur]);
					cur = r[cur];
				}
				
				reverse(all(tmp));
				sr.pop_back();
				for(auto u : tmp){
					sr.pb(u);
				}
			}
			
			while(!sl.empty() && sl.back().first < v[i]){
				sl.pop_back();
			}
			sl.pb(mp(v[i], i));
			if(sl.size() == 1){
				t.rs(1, 0, i, v[i]);
			}
			else{
				t.rs(1, l[i] + 1, i, v[i]);
			}
			curans = min(curans, t.sq(1, 0, n-1));
		}
		
		ans[tt] = curans;
		// cout<<'\n';
	}
	
	return ans;
}

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