oj.uz

답안 #792511

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
792511 2023-07-25T06:12:51 Z 박상훈(#10052) Real Mountains (CCO23_day1problem2) C++17
0 / 25
 14 ms 23800 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef long long ll;

constexpr ll INF = 4e18;
constexpr int MOD = 1e6 + 3;

int n;
ll a[1001000], b[1001000];
vector<array<int, 2>> Ev[1001000];

struct Seg{
	ll tree[2002000];
	int sz;

	void init(int n){
		sz = n;
		for (int i=sz;i<sz*2;i++) tree[i] = a[i-sz];
		for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
	}

	void update(int p, ll x){
		p += sz;
		tree[p] = x;
		for (p>>=1;p;p>>=1) tree[p] = min(tree[p<<1], tree[p<<1|1]);
	}

	ll query(int l, int r){
		++r;
		ll ret = INF;
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1) ret = min(ret, tree[l++]);
			if (r&1) ret = min(ret, tree[--r]);
		}

		return ret;
	}
}tree;

void genB(){
	int idx = max_element(a+1, a+n+1) - a;
	
	int cur = 0;
	for (int i=1;i<=idx;i++){
		if (cur <= a[i]){
			b[i] = a[i];
			cur = a[i];
		}

		else b[i] = cur;
	}

	cur = 0;
	for (int i=n;i>=idx;i--){
		if (cur <= a[i]){
			b[i] = a[i];
			cur = a[i];
		}

		else b[i] = cur;
	}
}

ll rans;
int cnt;
void dfs(vector<int> A, ll cur){
	cnt++;
	if (cnt > 1e5) {rans = -1; return;}
	// for (auto &x:A) printf("%d ", x);
	// printf("-> %lld\n", cur);

	int idx = max_element(A.begin(), A.end()) - A.begin();
	bool flag = 1;
	for (int i=0;i<idx;i++) if (A[i] > A[i+1]) flag = 0;
	for (int i=(int)A.size()-1;i>idx;i--) if (A[i] > A[i-1]) flag = 0;

	if (flag){
		// printf("ok cur = %lld\n", cur);
		rans = min(rans, cur);
		return;
	}

	for (int i=0;i<(int)A.size();i++){
		for (int j=i+1;j<(int)A.size();j++){
			for (int k=j+1;k<(int)A.size();k++){
				cnt++;
				if (cnt > 1e5) {rans = -1; return;}

				if (A[i] > A[j] && A[j] < A[k]){
					cur += A[i] + A[j] + A[k];
					A[j]++;

					dfs(A, cur);

					A[j]--;
					cur -= A[i] + A[j] + A[k];

				}

				// if (i==0 && j==1 && k==6) printf("ok %d %d %d\n", A[i], A[j], A[k]);
			} 
		}
	}
}

ll naive(){
	cnt = 0;
	vector<int> A;
	for (int i=1;i<=n;i++) A.push_back(a[i]);

	rans = INF;
	dfs(A, 0);
	
	return rans;
}

ll sum(ll l, ll r){
	assert(l<=r);
	assert(r < (int)(1e9 + 100));

	return (r*(r+1) / 2 - l*(l-1) / 2) % MOD;
}

ll solve(){
	a[0] = INF;

	// int H = *max_element(a+1, a+n+1);
	// for (int i=1;i<=H;i++) Ev[i].clear();

	// scanf("%d", &n);
	// for (int i=1;i<=n;i++) scanf("%lld", a+i);

	// printf("%lld\n", naive());

	genB();

	vector<int> C;
	for (int i=1;i<=n;i++){
		C.push_back(a[i]);
		C.push_back(b[i]);
	}

	C.push_back(0);
	sort(C.begin(), C.end());
	C.erase(unique(C.begin(), C.end()), C.end());
	
	for (int i=1;i<=n;i++){
		a[i] = lower_bound(C.begin(), C.end(), a[i]) - C.begin();
		b[i] = lower_bound(C.begin(), C.end(), b[i]) - C.begin();

		Ev[a[i]].push_back({0, i});
		Ev[b[i]].push_back({1, i});
		// assert(a[i] <= b[i]);
		// assert(b[i] <= H);
	}

	
	multiset<int> st;
	tree.init(n+1);
	ll ans = 0;

	for (int i=1;i<(int)C.size();i++){
		sort(Ev[i].begin(), Ev[i].end());

		for (auto &[typ, pos]:Ev[i]){
			if (typ==0){
				tree.update(pos, INF);
				st.insert(pos);
			}

			else{
				st.erase(st.find(pos));
			}
		}

		int cnt = st.size();
		if (cnt==0) continue;

		int s = *st.begin(), e = *st.rbegin();
		ll p0 = tree.query(1, s-1), pk = tree.query(e+1, n), p = tree.query(1, n);

		// printf("\n%d -> %d:\n", i, i+1);
		// for (auto &x:st) printf("%d ", x);
		// printf("\n");
		// printf(" ok %lld %lld %lld\n", p0, pk, p);

		assert(p0 < INF && pk < INF && p < INF);
		assert(p0 > i && pk > i && p > i);

		if (cnt >= 2){
			ans += (p0 + pk + p) * (C[i+1] - C[i]);
			ans %= MOD;

			ans += sum(C[i]+1, C[i+1]) * (cnt*2 - 3);
			ans %= MOD;

			ans += sum(C[i], C[i+1]-1) * cnt;
			ans %= MOD;
		}

		else{
			ans += (p0 + pk) * (C[i+1] - C[i]);
			ans %= MOD;

			ans += sum(C[i], C[i+1]-1) * cnt;
			ans %= MOD;
		}
		// if (cnt >= 2) ans += p0 + pk + p + (ll)(i+1) * (cnt*2 - 3) + (ll)i*cnt;
		// else ans += p0 + pk + i;

		// ans %= MOD;
	}

	return ans;
}

mt19937 seed(69);
uniform_int_distribution<int> rng(0, 2147483647);
int getrand(int l, int r){return rng(seed) % (r-l+1) + l;}

void gen(){
	n = getrand(1, 7);
	for (int i=1;i<=n;i++) a[i] = getrand(1, 10);
}

void stress(int tc){
	// printf("--------------------------------------\n");
	// printf("Stress #%d\n", tc);
	gen();

	// printf("Input:\n");
	// printf("%d\n", n);
	// for (int i=1;i<=n;i++) printf("%lld ", a[i]);
	// printf("\n");

	ll ans = naive();
	ll out = solve();
	// printf("Answer: %lld\n", ans);
	// printf("Output: %lld\n", out);

	if (ans!=out && ans!=-1){
		printf("--------------------------------------\n");
		printf("Stress #%d\n", tc);

		printf("Input:\n");
		printf("%d\n", n);
		for (int i=1;i<=n;i++) printf("%lld ", a[i]);
		printf("\n");

		printf("Answer: %lld\n", ans);
		printf("Output: %lld\n", out);
	}

	if (tc%10000==0) printf("ok %d done\n", tc);

	assert(ans==out || ans==-1);
}

signed main(){
	// for (int i=1;;i++) stress(i);

	scanf("%lld", &n);
	for (int i=1;i<=n;i++) scanf("%lld", a+i);
	printf("%lld\n", solve());
}

Compilation message

Main.cpp: In function 'void stress(long long int)':
Main.cpp:245:20: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  245 |   printf("Stress #%d\n", tc);
      |                   ~^     ~~
      |                    |     |
      |                    int   long long int
      |                   %lld
Main.cpp:248:12: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  248 |   printf("%d\n", n);
      |           ~^     ~
      |            |     |
      |            int   long long int
      |           %lld
Main.cpp:256:31: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  256 |  if (tc%10000==0) printf("ok %d done\n", tc);
      |                              ~^          ~~
      |                               |          |
      |                               int        long long int
      |                              %lld
Main.cpp: In function 'int main()':
Main.cpp:264:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  264 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
Main.cpp:265:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  265 |  for (int i=1;i<=n;i++) scanf("%lld", a+i);
      |                         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 14 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 14 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 14 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 14 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 14 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 14 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 14 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -