oj.uz

Submission #447860

# Submission time Handle Problem Language Result Execution time Memory
447860 2021-07-27T21:04:57 Z FEDIKUS Fancy Fence (CEOI20_fancyfence) C++17
100 / 100
 32 ms 3800 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

const int maxn=1e5+10;
const int mod=1e9+7;

int add(int a,int b){
    return (a+b)%mod;
}

int mul(int a,int b){
    return ll(a)*ll(b)%ll(mod);
}

int h[maxn];
int w[maxn];

int sta(int a){
    a++;
    if(a&1) return mul(a,(a-1)/2);
    else return mul(a/2,a-1);
}

void solve(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>h[i];
    for(int i=0;i<n;i++) cin>>w[i];
    stack<pii> stek;
    int sum=0;
    int res=0;
    for(int i=0;i<n;i++){
        int duz=w[i];
        int vis=h[i];
        while(!stek.empty() && stek.top().xx>=vis){
            auto [a,b]=stek.top();
            sum=add(sum,-mul(sta(a),b));
            duz=add(duz,b);
            stek.pop();
        }
        stek.push(mp(vis,duz));
        sum=add(sum,mul(sta(vis),duz));

        res=add(res,mul(sum,w[i]));
        res=add(res,-mul(sta(vis),mul(w[i],w[i])));
        res=add(res,mul(sta(vis),sta(w[i])));
    }
    cout<<(res+mod)%mod;
}

int main(){
    ios;
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 320 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 13 ms 1228 KB Output is correct
4 Correct 24 ms 2244 KB Output is correct
5 Correct 25 ms 2268 KB Output is correct
6 Correct 25 ms 2252 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 16 ms 1656 KB Output is correct
4 Correct 29 ms 3040 KB Output is correct
5 Correct 32 ms 3012 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 16 ms 1616 KB Output is correct
5 Correct 29 ms 3020 KB Output is correct
6 Correct 32 ms 3028 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 16 ms 1884 KB Output is correct
10 Correct 29 ms 3664 KB Output is correct
11 Correct 32 ms 3800 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #6
18.0 / 18.0

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

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 13 ms 1224 KB Output is correct
12 Correct 24 ms 2232 KB Output is correct
13 Correct 25 ms 2260 KB Output is correct
14 Correct 24 ms 2208 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 15 ms 1688 KB Output is correct
18 Correct 29 ms 3020 KB Output is correct
19 Correct 32 ms 3076 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 3 ms 588 KB Output is correct
22 Correct 16 ms 1868 KB Output is correct
23 Correct 29 ms 3732 KB Output is correct
24 Correct 31 ms 3724 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 3 ms 596 KB Output is correct
31 Correct 3 ms 588 KB Output is correct
32 Correct 15 ms 1484 KB Output is correct
33 Correct 15 ms 1660 KB Output is correct
34 Correct 29 ms 2848 KB Output is correct
35 Correct 29 ms 2772 KB Output is correct
36 Correct 30 ms 2976 KB Output is correct
37 Correct 30 ms 3000 KB Output is correct
38 Correct 0 ms 204 KB Output is correct
39 Correct 30 ms 2980 KB Output is correct
40 Correct 32 ms 2996 KB Output is correct
41 Correct 31 ms 3080 KB Output is correct
42 Correct 30 ms 3432 KB Output is correct