Submission #1163097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163097		pan	Real Mountains (CCO23_day1problem2)	C++20	25 / 25	3272 ms	384244 KiB

Main

#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
#pragma GCC optimize("O3","unroll-loops")
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll const INF = 1e18, mod = 1e6 + 3;
ll n, ans = 0;
ll a[1000005], b[1000005];
map<ll, vector<ll> > st, en;
set<ll> cur;


struct node {
    ll s, e, m; 
    ll val; 
    node * l, * r; 
    node(ll S, ll E) { 
        s = S, e = E, m = (s + e) / 2;
        if (s != e) { 
            l = new node(s, m); 
            r = new node(m + 1, e); 
            val = min(l->val, r->val);
        }
        else {val = a[s];}
    }
    void update(ll X, ll V) { 
        if (s == e) val = V;
        else { 
            if (X <= m) l -> update(X, V); 
            else r -> update(X, V); 
            val = min(l -> val, r -> val); 
        }
    }
    ll query(ll S, ll E) {
        if (s == S && e == E) return val;
        else if (E <= m) return l -> query(S, E);
        else if (S >= m + 1) return r -> query(S, E);
        else return min(l -> query(S, m), r -> query(m + 1, E));
    }
}* root;

ll cal(ll from, ll to)
{
	if (cur.empty()) return 0;
	ll l = *cur.begin(), r = *prev(cur.end());
	ll ans = ((root->query(1, l-1)%mod + root->query(r + 1, n)%mod) % mod)*(to-from)%mod;
	if (l==r) return ans;
	// assume size >= 2
	ans = (ans + (to * (to-from) % mod + ((2*(ll(cur.size())-2) + 1)%mod * ((to + 1)*to/2 % mod - (from + 1)*from/2 % mod + mod) % mod)%mod)%mod)%mod;
	return ans;
	
}


int main()
{
	cin >> n;
	for (ll i=1; i<=n; ++i) {cin >> a[i]; st[a[i]].pb(i);}
	root = new node(1, n);
	// calculate final array
	b[1] = a[1], b[n] = a[n];
	ll idx = max_element(a + 1, a + n + 1)-a;
	for (ll i=2; i<=idx; ++i) b[i] = max(b[i-1], a[i]);
	for (ll i=n-1; i>=idx; --i) b[i] = max(b[i+1], a[i]);
	for (ll i=1; i<=n; ++i) 
	{
		en[b[i]].pb(i); 
		ans = (ans + ((b[i]-1) * b[i]/2 % mod - (a[i]-1) * a[i]/2 % mod)%mod)%mod; // middle term solved!
		//show2(a[i], b[i]);
	}
	//show(ans);
	ll pp = -1;
	for (auto u: st)
	{
		//show(u.f);
		if (pp!=-1) ans = (ans + cal(pp, u.f))%mod;
		for (ll x: u.s)
		{
			//show(x);
			cur.insert(x);
			root->update(x, INF);
		}
		for (ll x: en[u.f]) cur.erase(x);
		pp = u.f;
	}
	cout << ans << endl;
	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 4 / 4