oj.uz

Submission #945910

# Submission time Handle Problem Language Result Execution time Memory
945910 2024-03-14T08:39:41 Z teacup Fancy Fence (CEOI20_fancyfence) C++17
30 / 100
 9 ms 2396 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
typedef vector<int> vi;
#define iii tuple<int,int,int>
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef map<int,int> mii;

#ifndef debug
	#define cerr if (0) cerr
#endif
int N,H[10005],W[10005];
int pref[10005], last_mins[10005];
const int mod=1e9+7;
int nc2(int n){
	return ((n*(n-1))/2)%mod;
}
int rect(int h, int w){
	return (nc2(h+1)*nc2(w+1))%mod;
}
struct node{
	int s,e,mn,mx,sum,add_val,set_val;
	bool lset;
	node *l, *r;
	node (int _s, int _e, int A[]=NULL): s(_s), e(_e), mn(0), mx(0), sum(0), lset(0), add_val(0), set_val(0), l(NULL), r(NULL){
		if (A==NULL) return;
		if (s==e) mn=mx=sum=A[s];
		else{
			l=new node(s, (s+e)>>1,A), r=new node((s+e+2)>>1,e,A);
			combine();
		}
	}
	void create_children(){
		if (s==e) return;
		if (l!=NULL) return;
		int m=(s+e)>>1;
		l=new node(s,m);
		r=new node(m+1,e);
	}
	void self_set(int v){
		lset=1;
		mn=mx=set_val=v;
		sum=v*(e-s+1);
		add_val=0;
	}
	void self_add(int v){
		if (lset) {self_set(v+set_val); return;}
		mn+=v, mx+=v, add_val+=v;
		sum+=v*(e-s+1);
	}
	void lazy(){
		if (s==e) return;
		if (lset){
			l->self_set(set_val), r->self_set(set_val);
			set_val=0; lset=0;
		}
		if (add_val!=0){
			l->self_add(add_val), r->self_add(add_val);
			add_val=0;
		}
	}
	void combine(){
		if (l==NULL) return;
		sum=l->sum +r->sum;
		mn=min(l->mn,r->mn);
		mx=max(l->mx,r->mx);
	}
	#define UPDATE(name)\
	void name(int x, int y, int v){\
		if (s==x&&e==y) {self_##name(v); return;}\
		int m=(s+e)>>1; \
		create_children(); lazy();\
		if (x<=m) l->name(x,min(y,m),v);\
		if (y>m) r->name(max(x,m+1),y,v);\
		combine();\
	}
	UPDATE(add)
	UPDATE(set)
	#define QUERY(name,fn,var,lazyfn)\
	int range_##name(int x, int y){\
		if (s==x&&e==y) return var;\
		if (l==NULL||lset) return lazyfn(var);\
		int m=(s+e)>>1; lazy();\
		if (y<=m) return l->range_##name(x,y);\
		if (x>m) return r->range_##name(x,y);\
		return fn(l->range_##name(x,m), r->range_##name(m+1,y));\
	}
	#define SAME(var) (var)
	#define PART(var) ((var)/(e-s+1)*(y-x+1))
	#define SUM(a,b) ((a)+(b))
	QUERY(min,min,mn,SAME)
	QUERY(max,max,mx,SAME)
	QUERY(sum,SUM,sum,PART)
	~node(){
		if (l!=NULL) delete l;
		if (r!=NULL) delete r;
	}
}*root;

int32_t main(){
	cin>>N;
	int last_min = -1;
	for (int i=0; i<N; i++)cin>>H[i];
	for (int i=0; i<N; i++){
		cin>>W[i];
		if (i==0) pref[i]=W[i];
		else pref[i]=W[i]+pref[i-1];
		
		last_mins[i]=last_min;
		if (i>0 && H[i-1]>H[i]){
			last_min = i;
		}
	}
	
	root = new node(0,N-1,H);
	
	int ans=0, sum=0;
	stack<iii> st;
	for (int i=0; i<N; i++){
		ans += rect(H[i],W[i]);
		ans %= mod;
		
		int total_w = 0;
		while (st.size() && get<0>(st.top()) >= H[i]){
			auto [h,w,p] = st.top();
			st.pop();
			total_w += w;
			total_w %= mod;
			sum = (sum-p + mod);
			sum %= mod;
		}
		ans += (sum*W[i])%mod;
		ans %= mod;
		ans += total_w * nc2(H[i]+1)%mod * W[i]%mod;
		ans %= mod;
		total_w += W[i];
		total_w %= mod;
		int t = total_w * nc2(H[i]+1);
		t %= mod;
		sum += t;
		sum %= mod;
		st.push({H[i], total_w, t});
	}
	cout<<ans;
}

Compilation message

fancyfence.cpp: In constructor 'node::node(long long int, long long int, long long int*)':
fancyfence.cpp:25:7: warning: 'node::lset' will be initialized after [-Wreorder]
   25 |  bool lset;
      |       ^~~~
fancyfence.cpp:24:20: warning:   'long long int node::add_val' [-Wreorder]
   24 |  int s,e,mn,mx,sum,add_val,set_val;
      |                    ^~~~~~~
fancyfence.cpp:27:2: warning:   when initialized here [-Wreorder]
   27 |  node (int _s, int _e, int A[]=NULL): s(_s), e(_e), mn(0), mx(0), sum(0), lset(0), add_val(0), set_val(0), l(NULL), r(NULL){
      |  ^~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #2
12.0 / 12.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 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 7 ms 2396 KB Output is correct
3 Runtime error 4 ms 860 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 9 ms 2392 KB Output is correct
4 Runtime error 4 ms 860 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 464 KB Output is correct
16 Correct 1 ms 344 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 616 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Incorrect 1 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -