oj.uz

Submission #304639

# Submission time Handle Problem Language Result Execution time Memory
304639 2020-09-21T16:15:15 Z nicolaalexandra Fancy Fence (CEOI20_fancyfence) C++14
30 / 100
 203 ms 5368 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++){
        int 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();
        }

        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] + latime) % MOD));
    }

    cout<<(sol+MOD)%MOD;


    return 0;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 2 ms 384 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 3 ms 384 KB Output is correct
2 Correct 20 ms 640 KB Output is correct
3 Correct 97 ms 2064 KB Output is correct
4 Correct 203 ms 3960 KB Output is correct
5 Correct 188 ms 3956 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 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 18 ms 640 KB Output is correct
4 Correct 89 ms 2092 KB Output is correct
5 Correct 170 ms 3808 KB Output is correct
6 Correct 181 ms 3960 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 18 ms 888 KB Output is correct
9 Correct 99 ms 2424 KB Output is correct
10 Correct 165 ms 5368 KB Output is correct
11 Correct 173 ms 5368 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 256 KB Output isn't correct
7 Halted 0 ms 0 KB -