oj.uz

Submission #623672

# Submission time Handle Problem Language Result Execution time Memory
623672 2022-08-06T09:13:29 Z Vladth11 Fancy Fence (CEOI20_fancyfence) C++14
30 / 100
 37 ms 9980 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 100001;
const ll VMAX = 101;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 117;
const ll nr_of_bits = 18;
const ll inv2 = 500000004;

pii stiva[NMAX];
ll vf;
ll scor = 0;
ll h[NMAX];
ll w[NMAX];

ll lgput(ll n, ll p){
    ll rez = 1;
    while(p){
        if(p % 2){
            rez = (1LL * rez * n) % MOD;
        }
        n = (1LL * n * n) % MOD;
        p /= 2;
    }
    return rez;
}

ll gauss(ll x){
    return 1LL * (1LL * x * (x + 1)) % MOD * inv2 % MOD;
}

ll cate(ll h, ll w){
    return (1LL * gauss(h) * gauss(w)) % MOD;
}

ll combined(ll h, ll w1, ll w2){
    return (1LL * (1LL * gauss(h) * w1) % MOD * w2) % MOD;
}

void add(ll &x, ll val){
    x += val;
    if(x >= MOD){
        x -= MOD;
    }
    if(x < 0){
        x += MOD;
    }
}

unordered_map <int, ll> mp;

int main() {
    //ifstream cin(".in");
    //ofstream cout(".out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, i;
    ll total = 0;
    cin >> n;
    for(i = 1; i <= n; i++) cin >> h[i];
    for(i = 1; i <= n; i++) cin >> w[i];
    for(i = 1; i <= n; i++){
        add(total, cate(h[i], w[i]));
        ll avem = w[i];
        while(vf && stiva[vf].first >= h[i]){
            add(total, combined(h[i], stiva[vf].second, w[i]));
            add(avem, stiva[vf].second);
            vf--;
        }
        stiva[++vf] = {h[i], avem};
    }
    vf = 0;
    for(i = n; i >= 1; i--){
        ll avem = w[i];
        while(vf && stiva[vf].first >= h[i]){
            add(total, combined(h[i], stiva[vf].second, w[i]));
            add(avem, stiva[vf].second);
            vf--;
        }
        stiva[++vf] = {h[i], avem};
    }
    for(i = 1; i <= n; i++){
        add(total, -combined(h[i], mp[h[i]], w[i]));
        add(mp[h[i]], w[i]);
    }
    //debug(total);
    cout << total;
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 0 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 0 ms 212 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 0 ms 340 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 13 ms 1236 KB Output is correct
4 Correct 26 ms 1996 KB Output is correct
5 Correct 30 ms 2004 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 14 ms 1252 KB Output is correct
5 Correct 27 ms 1976 KB Output is correct
6 Correct 28 ms 1964 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 4 ms 1108 KB Output is correct
9 Correct 15 ms 2340 KB Output is correct
10 Correct 36 ms 8180 KB Output is correct
11 Correct 37 ms 9980 KB Output is correct
12 Correct 0 ms 332 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -