Submission #968041

#	Time	Username	Problem	Language	Result	Execution time	Memory
968041		pcc	Real Mountains (CCO23_day1problem2)	C++17	0 / 25	2 ms	2652 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")


#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
#define int ll

const ll mod = 1e6+3;
const int inf = 1e9;
const int mxn = 1e6+10;
int arr[mxn],pref[mxn],suf[mxn],tar[mxn];
ll ans = 0;
int N;
vector<int> all;

void up(int id){
	vector<int> v;
	for(int i = 1;i<=N;i++){
		if(arr[i] == all[id]&&tar[i] != arr[i])v.push_back(i);
	}
	if(v.empty())return;
	pii ls = pii(inf,inf),rs = pii(inf,inf);
	for(int i = 1;i<=N;i++){
		if(arr[i]<=all[id])continue;
		if(i<v[0])ls.fs = min(ls.fs,arr[i]);
		else ls.sc = min(ls.sc,arr[i]);
		if(i<v.back())rs.fs = min(rs.fs,arr[i]);
		else rs.sc = min(rs.sc,arr[i]);
	}
	if(v.size() == 1){
		ans += (ls.fs+ls.sc)*(all[id+1]-all[id])+(all[id]+all[id+1]-1)*(all[id+1]-all[id])/2%mod;
		ans %= mod;
		arr[v[0]] = all[id+1];
		return;
	}
	if(ls.fs+ls.sc+rs.sc<=rs.fs+rs.sc+ls.fs){
		ans += (ls.fs+ls.sc)*(all[id+1]-all[id])%mod;
		ans += rs.sc*(all[id+1]-all[id])%mod+(all[id+1]+all[id]+1)*(all[id+1]-all[id])/2%mod;
	}
	else{
		ans += (rs.fs+rs.sc)*(all[id+1]-all[id])%mod;
		ans += ls.fs*(all[id+1]-all[id])%mod+(all[id+1]+all[id]+1)*(all[id+1]-all[id])/2%mod;
	}
	ans %= mod;
	ans += 1ll*(v.size()-2)*((all[id+1]+all[id]+1)*(all[id+1]-all[id])/2%mod*2)%mod;
	ans += 1ll*v.size()*((all[id+1]-1+all[id])*(all[id+1]-all[id])/2%mod)%mod;
	for(auto &i:v)arr[i] = all[id+1];
	return;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	arr[0] = arr[N+1] = 1e9;
	for(int i = 1;i<=N;i++)cin>>arr[i],all.push_back(arr[i]);
	all.push_back(arr[0]);
	sort(all.begin(),all.end());
	all.erase(unique(all.begin(),all.end()),all.end());
	int mx = 0;
	for(int i = 1;i<=N;i++){
		mx = max(arr[i],mx);
		tar[i] = mx;
	}
	mx = 0;
	for(int i = N;i>=1;i--){
		mx = max(arr[i],mx);
		tar[i] = min(tar[i],mx);
	}
	for(int i = 0;i+1<all.size();i++){
		up(i);
	}
	cout<<ans<<'\n';
	return 0;
}

Compilation message (stderr)

Main.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main(){
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:75:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i = 0;i+1<all.size();i++){
      |                ~~~^~~~~~~~~~~

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