Submission #526498

#	Time	Username	Problem	Language	Result	Execution time	Memory
526498		Tam_theguide	Fancy Fence (CEOI20_fancyfence)	C++14	0 / 100	1 ms	312 KiB

fancyfence

//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 (stderr)

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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27