oj.uz

Submission #969485

# Submission time Handle Problem Language Result Execution time Memory
969485 2024-04-25T08:32:58 Z willychan Real Mountains (CCO23_day1problem2) C++17
0 / 25
 1 ms 356 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long llo;
//#include<bits/extc++.h>
//__gnu_pbds

const int MOD = 1e6+3;
/*
mantain a set of in process elements
repeatly remove elements from the leftmost or the rightmost side for which there doesn't exist a i<j<k such that hi>hj<hk
if(cnt>=2):
check for 4 number ll lr rl rr
some inequality
rl <= ll 
lr <= rr
pick the smallest of rl,lr M
than suppose the current height is h, and there are cnt element in my set
let L = (M-h)
ans+= L(ll+M+rr+2*cnt-3)+(3*cnt-4)*(L*(h+M-1))/2;
h = M;

else:
find 2 numbers l, r
WLOG l<=r
ans += (h+l-1)(l-h)/2 + (l+r)(l-h)
*/

struct SEG{
	vector<int> arr;
	int n;
	void init(int _n){
		n = _n;	
		arr.resize(4*n,0);
	}
	void modify(int x,int v,int L,int R,int ind){
		if(R==L){
			arr[ind]=v;
			return;
		}
		int M = (L+R)/2;
		if(x<=M) modify(x,v,L,M,2*ind);
		else modify(x,v,M+1,R,2*ind+1);
		arr[ind] = min(arr[2*ind],arr[2*ind+1]);
	}
	int query(int l,int r,int L,int R,int ind){
		if(l==L && r==R) return arr[ind];
		int M = (L+R)/2;
		if(r<=M) return query(l,r,L,M,2*ind);
		if(l>M) return query(l,r,M+1,R,2*ind+1);
		return min(query(l,M,L,M,2*ind),query(M+1,r,M+1,R,2*ind+1));
	}
} seg;

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;cin>>n;
	seg.init(n);
	vector<int> h(n);
	vector<int> d;
	for(int i=0;i<n;i++){
		cin>>h[i];
		seg.modify(i,h[i],0,n-1,1);
		d.push_back(h[i]);
	}
	sort(d.begin(),d.end());
	d.resize(unique(d.begin(),d.end())-d.begin());
	vector<vector<int> > V(d.size());	
	for(int i=0;i<n;i++){
		int l = lower_bound(d.begin(),d.end(),h[i])	-d.begin();
		V[l].push_back(i);
	}
	llo ans = 0;
	set<int> s;
	for(int F=0;F<d.size();F++){
		for(auto i : V[F]){
			s.insert(i);
			seg.modify(i,1e9+5,0,n-1,1);
		}
		int H = d[F];
		while(s.size()){
			int cur = *s.begin();
			int l = seg.query(0,cur,0,n-1,1);
			int r = seg.query(cur,n-1,0,n-1,1);
			if((l>1e9 || l<=H) || (r>1e9 || r<=H)) s.erase(cur);
			else break;
		}
		while(s.size()){
			int cur = *s.rbegin();
			int l = seg.query(0,cur,0,n-1,1);
			int r = seg.query(cur,n-1,0,n-1,1);
			if((l>1e9 || l<=H) || (r>1e9 || r<=H)) s.erase(cur);
			else break;
		}
		if(s.size()==1){
			int cur = *s.begin();
			int l = seg.query(0,cur,0,n-1,1);
			int r = seg.query(cur,n-1,0,n-1,1);
			if(l>r)	swap(l,r);
			ans = ((ans+(1LL*(H+l-1)*(l-H)/2)%MOD)%MOD + ((1LL*(l+r)*(l-H))%MOD))%MOD;
		}else if(s.size()>1){
			int cnt = s.size();
			int ll = seg.query(0,*s.begin(),0,n-1,1);
			int lr = seg.query(*s.begin(),n-1,0,n-1,1);
			int rl = seg.query(0,*(s.rbegin()),0,n-1,1);
			int rr = seg.query(*(s.rbegin()),n-1,0,n-1,1);
			int M = max(lr,rl);
			int L = (M-H);
			ans = (ans+(1LL*L*(((((ll+M)%MOD+rr)%MOD)+(2LL*cnt-3)%MOD)%MOD))%MOD)%MOD;
			ans = (ans+(1LL*(3*cnt%MOD-4)*((1LL*L*(H+M-1)/2)%MOD))%MOD)%MOD;
		}
	}
	ans%=MOD;
	if(ans<0) ans+=MOD;
	cout<<ans<<"\n";
	
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:74:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int F=0;F<d.size();F++){
      |              ~^~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 356 KB Output isn't correct
4 Halted 0 ms 0 KB -