Submission #55022276

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n)  for(int i=0;i<(n);++i)
#define sizc(x) ((int)x.size())
#define allc(x) x.begin(),x.end()
#define fir first
#define sec second
namespace KnownError_{
    constexpr int N = 3e5+5;
    int n,m,a[N];
    int st[20][N];
    int mx[N],ans[N];
    int amax(int x,int y){return a[x]>a[y]?x:y;}
    vector<pair<int,int>> Q1[N],Q2[N];
    int stk[N],tp;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n)  for(int i=0;i<(n);++i)
#define sizc(x) ((int)x.size())
#define allc(x) x.begin(),x.end()
#define fir first
#define sec second
namespace KnownError_{
    constexpr int N = 3e5+5;
    int n,m,a[N];
    int st[20][N];
    int mx[N],ans[N];
    int amax(int x,int y){return a[x]>a[y]?x:y;}
    vector<pair<int,int>> Q1[N],Q2[N];
    int stk[N],tp;
    ll t[N<<1],tg[N<<1];
    void bd(int u,int L,int R){
        tg[u]=0;
        if(L==R){t[u]=a[L];return;}
        int M=L+R>>1,ls=M<<1,rs=M<<1|1;
        bd(ls,L,M),bd(rs,M+1,R);
        t[u]=min(t[ls],t[rs]);
    }
    void add(int u,int L,int R,int l,int r,int x){
        if(r<L||R<l||r<l)return;
        if(l<=L&&R<=r){t[u]+=x,tg[u]+=x;return;}
        int M=L+R>>1,ls=M<<1,rs=M<<1|1;
        add(ls,L,M,l,r,x),add(rs,M+1,R,l,r,x);
        t[u]=min(t[ls],t[rs])+tg[u];
    }
    ll qry(int u,int L,int R,int l,int r){
        if(r<L||R<l||r<l)return 1e18;
        if(l<=L&&R<=r)return t[u];
        int M=L+R>>1,ls=M<<1,rs=M<<1|1;
        return min(qry(ls,L,M,l,r),qry(rs,M+1,R,l,r))+tg[u];
    }
    void main(){
    	cin>>n>>m;
        rep(i,1,n)cin>>a[i],st[0][i]=i;
        for(int j=1;(1<<j)<=n;++j)rep(i,1,n-(1<<j)+1)st[j][i]=amax(st[j-1][i],st[j-1][i+(1<<j-1)]);
        rep(i,1,m){
            int l,r;
            cin>>l>>r;
            int k=__lg(r-l+1);
            int p=amax(st[k][l],st[k][r-(1<<k)+1]);
            mx[i]=p;
            ans[i]=1e9;
            if(l<p&&p<r)ans[i]=a[l]+a[p]+a[r];
            if(p-l>1)Q1[l].emplace_back(p-1,i);
            if(r-p>1)Q2[r].emplace_back(p+1,i);
        }
        stk[0]=n+1;
        bd(1,1,n);
        per(i,n,1){
            while(tp&&a[stk[tp]]<=a[i]){
                add(1,1,n,stk[tp]+1,min(n,stk[tp-1]),-a[stk[tp]]);
                --tp;
            }
            add(1,1,n,i+1,min(n,stk[tp]),a[i]);stk[++tp]=i;
            for(auto p:Q1[i]){
                int t=p.fir,id=p.sec;
                ans[id]=min(ans[id],(int)qry(1,1,n,i+1,t)+a[mx[id]]);
            }
        }
        stk[tp=0]=0;bd(1,1,n);
        rep(i,1,n){
            while(tp&&a[stk[tp]]<=a[i]){
                add(1,1,n,max(1,stk[tp-1]),stk[tp]-1,-a[stk[tp]]);
                --tp;
            }
            add(1,1,n,max(1,stk[tp]),i-1,a[i]);stk[++tp]=i;
            for(auto p:Q2[i]){
                int t=p.fir,id=p.sec;
                ans[id]=min(ans[id],(int)qry(1,1,n,t,i-1)+a[mx[id]]);
            }
        }
        rep(i,1,m)cout<<ans[i]<<'\n';
    }
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    KnownError_::main();
}

Submission Info

Compile Error

Main.cpp: In function ‘void KnownError_::bd(int, int, int)’:
Main.cpp:26:16: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   26 |         int M=L+R>>1,ls=M<<1,rs=M<<1|1;
      |               ~^~
Main.cpp: In function ‘void KnownError_::add(int, int, int, int, int, int)’:
Main.cpp:33:16: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   33 |         int M=L+R>>1,ls=M<<1,rs=M<<1|1;
      |               ~^~
Main.cpp: In function ‘ll KnownError_::qry(int, int, int, int, int)’:
Main.cpp:40:16: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   40 |         int M=L+R>>1,ls=M<<1,rs=M<<1|1;
      |               ~^~
Main.cpp: In function ‘void KnownError_::main()’:
Main.cpp:46:94: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
   46 |         for(int j=1;(1<<j)<=n;++j)rep(i,1,n-(1<<j)+1)st[j][i]=amax(st[j-1][i],st[j-1][i+(1<<j-1)]);
      |                                                                                             ~^~

Judge Result