oj.uz

Submission #647345

# Submission time Handle Problem Language Result Execution time Memory
647345 2022-10-02T09:24:05 Z myrcella Fancy Fence (CEOI20_fancyfence) C++17
30 / 100
 37 ms 3224 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

int n;
const int maxn  = 1e5+10;

int h[maxn],w[maxn];
queue <pii> q;

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	rep(i,0,n) cin>>h[i];
	rep(i,0,n) cin>>w[i];
	int ans = 0,sum = 0;
	rep(i,0,n) {
		int curw = w[i];
		while (!q.empty() and q.back().fi>=h[i]) {
			inc(curw,q.back().se);
			dec(sum,1ll*q.back().fi*(q.back().fi+1)/2%mod*q.back().se%mod);
			q.pop();
		}
		q.push({h[i],curw});
		inc(sum,1ll*h[i]*(h[i]+1)/2%mod*curw%mod);
		inc(ans,1ll*sum*w[i]%mod);
		dec(ans,(1ll*w[i]*(w[i]-1)/2%mod)*(1ll*h[i]*(h[i]+1)/2%mod)%mod);
//		debug(ans);
	}
	cout<<ans;
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 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 340 KB Output is correct
2 Incorrect 1 ms 340 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 344 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 14 ms 1620 KB Output is correct
4 Correct 25 ms 3036 KB Output is correct
5 Correct 37 ms 3132 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 356 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 12 ms 1612 KB Output is correct
5 Correct 26 ms 3036 KB Output is correct
6 Correct 28 ms 3020 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 600 KB Output is correct
9 Correct 14 ms 1876 KB Output is correct
10 Correct 30 ms 2876 KB Output is correct
11 Correct 29 ms 3224 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 340 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 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -