제출 #1147120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147120		koukirocks	Fire (JOI20_ho_t5)	C++20	100 / 100	714 ms	95380 KiB

ho_t5

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

int n,q;
struct op {
    ll l,r,t,v;
};

void print(op a) {
    cout<<a.l<<" "<<a.r<<" "<<a.v<<" "<<a.t<<" ";
}

void tri(int pos,int h,ll v,vector<op> &op1,vector<op> &op2) {
    // cout<<pos<<" "<<h<<" tri\n";
    op1.push_back({pos+h,2*n+2,h,-v});
    // print(op1.back());cout<<"tri1\n";
    op2.push_back({pos,2*n+2,h,v});
    // print(op2.back());cout<<"tri2\n";
}

void para(int pos,int h,int w,ll v,vector<op> &op1,vector<op> &op2) {
    // cout<<pos<<" "<<h<<" "<<w<<" para\n";
    if (h>1) tri(pos-h+1,h-1,-v,op1,op2);
    if (w>1) tri(pos+1,w-1,-v,op1,op2);
    tri(pos-h+1,w+h-1,v,op1,op2);
}

struct SEG {
    int n;
    vector<ll> tree,lazy;
    SEG(int _n):n(_n) {
        tree.resize(4*n+10);
        lazy.resize(4*n+10);
    }
    void pd(int l,int r,int id) {
        int mid=l+r>>1;
        tree[id<<1]+=lazy[id]*(mid-l+1);
        lazy[id<<1]+=lazy[id];
        tree[id<<1|1]+=lazy[id]*(r-mid);
        lazy[id<<1|1]+=lazy[id];
        lazy[id]=0;
    }
    void update(int l,int r,int id,int L,int R,ll val) {
        // cout<<l<<" "<<r<<" "<<L<<" "<<R<<" lr LR\n";
        if (L<=l and r<=R) {
            tree[id]+=val*(r-l+1);
            lazy[id]+=val;
            return;
        }
        int mid=l+r>>1;
        pd(l,r,id);
        if (L<=mid) update(l,mid,id<<1,L,R,val);
        if (mid<R) update(mid+1,r,id<<1|1,L,R,val);
        tree[id]=tree[id<<1]+tree[id<<1|1];
    }
    ll query(int l,int r,int id,int L,int R) {
        if (L<=l and r<=R) return tree[id];
        int mid=l+r>>1;
        pd(l,r,id);
        ll ans=0;
        if (L<=mid) ans+=query(l,mid,id<<1,L,R);
        if (mid<R) ans+=query(mid+1,r,id<<1|1,L,R);
        return ans;
    }
};

int main() {
    speed;
    cin>>n>>q;
    int N=2*n+2;
    vector<ll> s(N);
    for (int i=1;i<=n;i++) {
        cin>>s[i+n+1];
    }
    vector<op> op1;
    vector<op> op2;
    vector<ll> lft(N),rt(N);
    vector<pll> stk;
    for (int i=n+2;i<=2*n+1;i++) {
        while (!stk.empty() and stk.back().F<s[i]) stk.pop_back();
        if (stk.empty()) lft[i]=n+1;
        else lft[i]=i-stk.back().S;
        stk.push_back({s[i],i});
        // cout<<lft[i]<<" "<<i<<" lft\n";
    }
    stk.clear();
    for (int i=2*n+1;i>=n+2;i--) {
        while (!stk.empty() and stk.back().F<=s[i]) stk.pop_back();
        if (stk.empty()) rt[i]=2*n+2;
        else rt[i]=stk.back().S;
        rt[i]-=i;
        stk.push_back({s[i],i});
        // cout<<rt[i]<<" "<<i<<" rt\n";
    }
    for (int i=n+2;i<=2*n+1;i++) {
        // cout<<i<<" "<<lft[i]<<" "<<rt[i]<<"\n";
        para(i,lft[i],rt[i],s[i],op1,op2);
    }
    vector<op> Q(q);
    for (int i=0;i<q;i++) {
        ll l,r,t;
        cin>>t>>l>>r;
        Q[i]={l+n+1,r+n+1,t+1,i};
    }
    auto cmp=[&](op a,op b) {
        return a.t<b.t;
    };
    sort(all(Q),cmp);
    sort(all(op1),cmp);
    sort(all(op2),cmp);
    SEG s1(N),s2(N);
    for (auto OP:op1) {
        s1.update(1,N,1,OP.l,OP.r,OP.v);
        // cout<<OP.l<<" "<<OP.r<<" "<<OP.t<<" "<<OP.v<<" op1 lrtv\n";
    }
    for (auto OP:op2) {
        s2.update(1,N,1,OP.l,OP.r,OP.v);
        // cout<<OP.l<<" "<<OP.r<<" "<<OP.t<<" "<<OP.v<<" op2 lrtv\n";
    }
    vector<ll> ans(q);
    int id1=0,id2=0;
    for (int i=0;i<q;i++) {
        while (id1<op1.size() and op1[id1].t<Q[i].t) {
            s1.update(1,N,1,op1[id1].l,op1[id1].r,-op1[id1].v);
            id1++;
        }
        while (id2<op2.size() and op2[id2].t<Q[i].t) {
            s2.update(1,N,1,op2[id2].l,op2[id2].r,-op2[id2].v);
            id2++;
        }
        ans[Q[i].v]=s1.query(1,N,1,Q[i].l,Q[i].r)+s2.query(1,N,1,Q[i].l-Q[i].t+1,Q[i].r-Q[i].t+1);
    }
    for (int i=0;i<q;i++) {
        cout<<ans[i]<<"\n";
    }
    return 0;
}

/*
5 1
2 4 3 2 1
5 1 5
*/

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80