oj.uz

Submission #304648

# Submission time Handle Problem Language Result Execution time Memory
304648 2020-09-21T16:35:24 Z nicolaalexandra Fancy Fence (CEOI20_fancyfence) C++14
100 / 100
 179 ms 5496 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define MOD 1000000007

using namespace std;

long long h[DIM],w[DIM];
deque<pair <long long,long long> > d;
int n,i;
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++)
        cin>>h[i];
    for (i=1;i<=n;i++)
        cin>>w[i];

    n++; /// mai adaug un dreptunghi fictiv

    d.push_back(make_pair(0,0));
    long long sol = 0;
    for (i=1;i<=n;i++){
        long long latime = 0;
        while (!d.empty() && h[i] < d.back().first){

            /// trb sa adun partea de sus care ar ramane cand scot asta din stiva
            long long h_ant = max (h[i],d[d.size()-2].first);
            long long dif = (d.back().first - h_ant + MOD) % MOD; /// inalimea partii de sus
            latime = (latime + d.back().second) % MOD;

            /// mai trb sa numar si dreptunghiurile care au inceputu in partea aia de sus si se continua in jos

            sol += ( dif * (dif + 1) / 2 % MOD + dif * h_ant % MOD) % MOD * (1LL * latime * (latime+1) / 2 % MOD) % MOD;
            sol %= MOD;

            d.pop_back();
        }

        w[i] = (w[i] + latime) % MOD;

        if (h[i] == d.back().first)
            d.back().second = (d.back().second + w[i]) % MOD;

        else d.push_back(make_pair(h[i],w[i]));
    }

    cout<<(sol+MOD)%MOD;


    return 0;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 56 ms 1656 KB Output is correct
4 Correct 112 ms 3064 KB Output is correct
5 Correct 114 ms 3064 KB Output is correct
6 Correct 112 ms 3064 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 18 ms 528 KB Output is correct
3 Correct 85 ms 1144 KB Output is correct
4 Correct 168 ms 1828 KB Output is correct
5 Correct 179 ms 2068 KB Output is correct
6 Correct 1 ms 256 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 17 ms 512 KB Output is correct
4 Correct 86 ms 1144 KB Output is correct
5 Correct 173 ms 1984 KB Output is correct
6 Correct 173 ms 1912 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 17 ms 640 KB Output is correct
9 Correct 90 ms 1528 KB Output is correct
10 Correct 167 ms 3448 KB Output is correct
11 Correct 174 ms 3448 KB Output is correct
12 Correct 0 ms 256 KB Output is correct

Subtask #6
18.0 / 18.0

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

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 56 ms 1656 KB Output is correct
12 Correct 112 ms 3192 KB Output is correct
13 Correct 116 ms 3064 KB Output is correct
14 Correct 114 ms 3064 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 17 ms 640 KB Output is correct
17 Correct 89 ms 2040 KB Output is correct
18 Correct 172 ms 3832 KB Output is correct
19 Correct 178 ms 3960 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 17 ms 768 KB Output is correct
22 Correct 89 ms 2552 KB Output is correct
23 Correct 163 ms 5368 KB Output is correct
24 Correct 170 ms 5496 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 18 ms 640 KB Output is correct
31 Correct 19 ms 640 KB Output is correct
32 Correct 79 ms 2044 KB Output is correct
33 Correct 87 ms 2040 KB Output is correct
34 Correct 159 ms 3704 KB Output is correct
35 Correct 157 ms 3572 KB Output is correct
36 Correct 175 ms 3832 KB Output is correct
37 Correct 175 ms 3832 KB Output is correct
38 Correct 1 ms 256 KB Output is correct
39 Correct 172 ms 3832 KB Output is correct
40 Correct 174 ms 3832 KB Output is correct
41 Correct 173 ms 3960 KB Output is correct
42 Correct 173 ms 4600 KB Output is correct