oj.uz

Submission #628803

# Submission time Handle Problem Language Result Execution time Memory
628803 2022-08-13T17:21:17 Z a_aguilo Fancy Fence (CEOI20_fancyfence) C++14
30 / 100
 1000 ms 1956 KB 
#include<bits/stdc++.h>

using namespace std;
typedef vector<int> vi;

const int MOD = 1e9 + 7;

void buildTree(int node, int leftBound, int rightBound, vi& arr, vi& tree){
    if(leftBound > rightBound) return;
    if(leftBound == rightBound) {
        tree[node] = arr[leftBound];
        return;
    }
    int mid = leftBound + (rightBound - leftBound)/2;
    buildTree(2*node, leftBound, mid, arr, tree);
    buildTree(2*node+1, mid+1, rightBound, arr, tree);
    tree[node] = min(tree[2*node], tree[2*node+1]);
}

int getValue(int node, int leftBound, int rightBound, int left, int right, vi& tree){
    if(left > rightBound or right < leftBound or leftBound > rightBound) return 1e9+7;
    if(left <= leftBound and right >= rightBound)return tree[node];
    int mid = leftBound + (rightBound - leftBound)/2;
    return min(getValue(2*node, leftBound, mid, left, right, tree), getValue(2*node+1, mid+1, rightBound, left, right, tree));
}

int main(){
    int n;
    long long W;
    cin >> n;
    vi heights(n);
    vi widths(n);
    for(int i = 0; i < n; ++i) cin >> heights[i];
    for(int i = 0; i < n; ++i)cin >> widths[i];

    vi tree(4*n, 1e9+7);
    buildTree(1, 0, n-1, heights, tree);

    long long ans = 0;
    for(int i = 0; i < n; ++i){
        for(int j = i; j < n; ++j){

            int H = getValue(1, 0, n-1, i, j, tree);
            //cout << i << " " << j << " " << H << " " << W << endl;
            long long chooseh = ((long long)H*(H+1)/2)%MOD;

            long long choosew;
            if(i == j) choosew = (((long long)widths[i]*(widths[i]+1))/2)%MOD;
            else choosew = ((long long)widths[i]*widths[j])%MOD;

            ans += (chooseh*choosew)%MOD;
            ans%=MOD;
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:29:15: warning: unused variable 'W' [-Wunused-variable]
   29 |     long long W;
      |               ^

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 66 ms 296 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 63 ms 212 KB Output is correct
3 Execution timed out 1074 ms 1356 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 212 KB Output is correct
2 Execution timed out 1087 ms 696 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 62 ms 296 KB Output is correct
3 Execution timed out 1087 ms 628 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 66 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 61 ms 304 KB Output is correct
9 Correct 66 ms 212 KB Output is correct
10 Correct 64 ms 320 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 14 ms 212 KB Output is correct
13 Correct 65 ms 212 KB Output is correct
14 Correct 68 ms 340 KB Output is correct
15 Correct 66 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 66 ms 296 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 71 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 232 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 66 ms 312 KB Output is correct
11 Execution timed out 1082 ms 1956 KB Time limit exceeded
12 Halted 0 ms 0 KB -