제출 #1172670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172670		nguyenkhangninh99	Art Exhibition (JOI18_art)	C++20	0 / 100	58 ms	117824 KiB

art

#include <bits/stdc++.h>

#pragma GCC optimize("O3")  
#pragma GCC optimize("unroll-loops")  
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define ii pair<int,int>

#define fi first
#define se second
#define pb push_back
const int N = (int)5e6+10;
ii a[N];
int n;

namespace sub4 {
	int preMin[N],preMax[N],sufMin[N],sufMax[N],par[N];
	ii pos[N];
	int L[N];
	vector<ii> q[N];

	int acs(int &u)
	{
		return (par[u] < 0 ? u : par[u] = acs(par[u]));
	}

	void solve(void)
	{
		preMin[0] = sufMin[n+1] = 1e9;
		preMax[0] = sufMax[n+1] = -1e9;
		FOR(i,1,n) 
		{
			preMin[i] = min(preMin[i-1],a[i].se); 
			preMax[i] = max(preMax[i-1],a[i].se);
		}
		FOD(i,n,1)
		{
			sufMin[i] = min(sufMin[i+1],a[i].se);
			sufMax[i] = max(sufMax[i+1],a[i].se);
		}
		int i = 1, j = 0, j2 = 0, ans = 1e9;
		while (i <= n)
		{
			while (j < n and preMax[j+1] <= sufMax[i+1]) ++j;
			while (j2 < n and preMin[j2+1] >= sufMin[i+1]) ++j2;
			while (j and preMax[j] > sufMax[i+1]) --j;
			while (j2 and preMin[j2] < sufMin[i+1]) --j2;
			pos[i] = {j,j2};
			i++;
		}
		FOR(k,0,3)
		{
			FOR(i,1,n) par[i] = -1;
			FOR(i,1,n)
			{
				if (!k) L[i] = (i > 1?-a[i].fi+preMax[i-1]-preMin[i-1]:1e9);
				if (k == 1) L[i] = (i < n?-a[i].fi:1e9);	
				if (k == 2) L[i] = (i > 1 and i < n?-a[i].fi+preMax[i-1]:1e9);
				if (k == 3) L[i] = (i > 1 and i < n?-a[i].fi-preMin[i-1]:1e9);
				int j = pos[i].fi, j2 = pos[i].se;
				int pos1 = max(j,j2)+2, pos2 = min(j,j2)+1;
				if (!k and pos1 <= i and i > 1) q[i].pb({pos1,i});
				if (k == 1 and pos2 and i < n) q[pos2].pb({1,i});
				if (k == 2 and i > 1 and i < n and j+2 <= min(j2+1,i)) q[min(j2+1,i)].pb({j+2,i});
				if (k == 3 and i > 1 and i < n and j2+2 <= min(j+1,i)) q[min(j+1,i)].pb({j2+2,i});
			}
			stack<int> st;
			FOR(i,1,n)
			{
				while (!st.empty() and L[st.top()] > L[i])
				{
					par[st.top()] = i;
					st.pop();
				}
				st.push(i);
				for (auto x : q[i])
				{
					int sum = 0;
					if (k == 1) sum = sufMax[x.se+1]-sufMin[x.se+1];
					if (k == 2) sum = -sufMin[x.se+1];
					if (k == 3) sum = sufMax[x.se+1];
					// cout << sum << " " << L[acs(x.fi)] << endl;
					ans = min(ans, sum+L[acs(x.fi)]+a[x.se].fi);
				}
				q[i].clear();
			}
		}
		cout << ans;
	}

}

signed main(){
    fast;
    cin >> n;
    FOR(i,1,n) cin >> a[i].fi >> a[i].se;
    sub4::solve();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50