oj.uz

Submission #526498

# Submission time Handle Problem Language Result Execution time Memory
526498 2022-02-15T03:34:02 Z Tam_theguide Fancy Fence (CEOI20_fancyfence) C++14
0 / 100
 1 ms 312 KB 
//dung stack de tim voi tat ca cac phan tu trong mang:
//phan tu gan nhat ve phia ben trai nho hon a[i]/lon hon a[i];
//stack chi tim duoc gan nhat
//tinh chat monotone:
//gia su khi them vao phan tu a[i] ta pop stack den phan tu a[j] thi cac phan tu a[t] sao cho j<t<i la mot day don dieu (MONOTONE)
//do ta pop tu a[i] den a[j] va pop het cac phan tu a[t] suy ra cac phan tu a[t] phai cung thoa man mot tinh chat nao neu khong thi khi them vao mot phan tu trong doan a[t] thi ta buoc phai pop mot so phan tu khac do mau thuan ve tinh chat
//there is a classic stack problem calls max rectangle area under histogram
//while doing a stack problem you can process the answer right at the moment that you cin>>input
//#pragma optimize("O2")
#include <bits/stdc++.h>
using namespace std;
int n;
int h[100005], w[100005];
vector<pair<int, int>>inc;
int cnt=0;
int ans=0;


int func(int h, int w){
    return (h*(h+1)/2)*(w*(w+1)/2);
}
int wid[100005];
int main(){
    cin>>n;
    for (int i=1;i <=n; i++){
        cin>>h[i];
    }
    for (int i=1;i <=n; i++){
        cin>>w[i];
    }
    for (int i=1;i <=n; i++){
        while (!inc.empty() && inc.back().first>=h[i]){
            w[i]+=inc.back().second;
            ans+=func(inc.back().first, inc.back().second)-func(h[i], inc.back().second);

            inc.pop_back();
        }
        inc.push_back(make_pair(h[i], w[i]));



    }
    wid[inc.size()-1]=inc[inc.size()-1].second;
    for (int i=inc.size()-2; i>=0; i--){
        wid[i]=wid[i+1]+inc[i].second;
    }
    ans+=func(inc[0].first, wid[0]);
    for (int i=1;i <inc.size(); i++){
        ans+=func(inc[i].first, wid[i])-func(inc[i-1].first, wid[i]);
    }
    cout<<ans;
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i=1;i <inc.size(); i++){
      |                  ~~^~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

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