oj.uz

Submission #646976

# Submission time Handle Problem Language Result Execution time Memory
646976 2022-10-01T09:35:50 Z jamielim Fancy Fence (CEOI20_fancyfence) C++14
30 / 100
 58 ms 20288 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n;
int h[100005],w[100005];

ll choose2(ll x){
	return ((x)*(x-1)/2)%MOD;
}

struct node{
	int s,e,m;
	ll ht,wd,val;
	ll lzht;
	node *l,*r;
	node(int S,int E){
		s=S;e=E;m=(s+e)/2;
		if(s==e){
			ht=h[s];
			wd=w[s];
			val=(wd*choose2(ht+1))%MOD;
		}else{
			l=new node(s,m);
			r=new node(m+1,e);
			ht=min(l->ht,r->ht);
			wd=l->wd+r->wd;
			val=l->val+r->val;
		}
	}
	void laze(){
		if(s!=e){
			l->lzht=lzht;
			r->lzht=lzht;
		}
		ht=lzht;
		val=(wd*choose2(ht+1))%MOD;
	}
	void upd(int x,int y,ll v){ // set height to be v for indices in [x,y]
		if(y<s||x>e||x>y)return;
		//printf("%d %d %lld\n",x,y,v);
		if(s<=x&&e<=y){
			lzht=v;
			laze();
			return;
		}
		laze();
		if(y<=m)l->upd(x,y,v);
		else if(x>m)r->upd(x,y,v);
		else l->upd(x,m,v),r->upd(m+1,y,v);
		l->laze();r->laze();
		ht=min(l->ht,r->ht);
		val=l->val+r->val;
	}
	ll qry(int x){ // sum of wd*((ht+1)C2) for indices <=x
		//printf("%d\n",x);
		if(x<s)return 0;
		if(s==e)return val;
		if(x<=m)return l->qry(x);
		return (l->val+r->qry(x))%MOD;
	}
}*root;

int main(){
	scanf("%d",&n);
	vector<int> v;
	for(int i=0;i<n;i++){
		scanf("%d",&h[i]);
		v.pb(h[i]);
	}
	for(int i=0;i<n;i++)scanf("%d",&w[i]);
	root=new node(0,n-1);
	ll ans=0;
	vector<ii> stk;
	stk.pb(-1,-1);
	for(int i=0;i<n;i++){
		// find leftmost value that is > h[i] and index <i
		int x=i;
		while(stk.back().fi>h[i]){
			x=stk.back().se;
			stk.pop_back();
		}
		stk.pb(h[i],i);
		root->upd(x,i-1,h[i]);
		
		ll cur=(root->qry(i-1))*(ll)(w[i]);
		cur%=MOD;
		ans+=cur; // left side is strictly from previous block, right side is (,] of current block
		ans%=MOD;
		ans+=((choose2(h[i]+1))*(choose2(w[i]+1)))%MOD; // left side is within current block
		ans%=MOD;
	}
	printf("%lld",ans%MOD);
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
fancyfence.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d",&h[i]);
      |   ~~~~~^~~~~~~~~~~~
fancyfence.cpp:85:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  for(int i=0;i<n;i++)scanf("%d",&w[i]);
      |                      ~~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 5 ms 2320 KB Output is correct
3 Correct 23 ms 10424 KB Output is correct
4 Correct 58 ms 20220 KB Output is correct
5 Correct 58 ms 20288 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 5 ms 2372 KB Output is correct
4 Correct 25 ms 10412 KB Output is correct
5 Correct 42 ms 20164 KB Output is correct
6 Correct 45 ms 20236 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 5 ms 2368 KB Output is correct
9 Correct 22 ms 10492 KB Output is correct
10 Correct 44 ms 20048 KB Output is correct
11 Correct 47 ms 20164 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -