oj.uz

답안 #525090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525090 2022-02-10T16:47:54 Z leaked 모임들 (IOI18_meetings) C++14
60 / 100
 5500 ms 245580 KB 
#include <bits/stdc++.h>
#include "meetings.h"


#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+1;
const ll inf=1e9;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
struct node{
    int mx=0;
    vec<int> cntl,cntr;
    vec<int>dpl,dpr;
    node(){
        cntl.assign(21,0);cntr=cntl;
        dpl.assign(21,inf);dpr=dpl;
        mx=-1;
    }
};
node mg(node a,node b){
    node c;
    c.mx=max(a.mx,b.mx);
    vec<int>cost(21,0),pcnt(21,0);
    ll sm=0;
    for(int i=0;i<=20;i++) pcnt[i]=(i?pcnt[i-1]:0)+b.cntl[i],cost[i]=(i?cost[i-1]:0)+b.cntl[i]*i;
    sm=cost[20];
    for(int i=0;i<sz(a.dpl);i++){
        int x=pcnt[i]*i+a.dpr[i]+sm-cost[i];
        int y=pcnt[a.mx]*a.mx+a.dpl[i]+sm-cost[a.mx];
        umin(c.dpl[i],y);umin(c.dpr[c.mx],y);
        umin(c.dpr[max(i,b.mx)],x);umin(c.dpl[a.mx],x);
    }

    for(int i=0;i<=20;i++) pcnt[i]=(i?pcnt[i-1]:0)+a.cntr[i],cost[i]=(i?cost[i-1]:0)+a.cntr[i]*i;
    sm=cost[20];
    for(int i=0;i<sz(b.dpl);i++){
        int x=pcnt[i]*i+b.dpl[i]+sm-cost[i];
        int y=pcnt[b.mx]*b.mx+b.dpr[i]+sm-cost[b.mx];
        umin(c.dpr[i],y);umin(c.dpl[c.mx],y);
        umin(c.dpl[max(i,a.mx)],x);umin(c.dpr[b.mx],x);
    }

    for(int i=0;i<=20;i++){
        c.cntr[max(i,b.mx)]+=a.cntr[i];
        c.cntr[i]+=b.cntr[i];
        c.cntl[max(i,a.mx)]+=b.cntl[i];
        c.cntl[i]+=a.cntl[i];
    }
    return c;
}
node t[4*N];
int a[N];
node emp;
void build(int v,int tl,int tr){
    if(tl==tr){
        t[v].cntl[a[tl]]=1;
        t[v].cntr[a[tl]]=1;
        t[v].mx=a[tl];
        t[v].dpl[a[tl]]=a[tl];
        t[v].dpr[a[tl]]=a[tl];
    }
    else{
        int tm=(tl+tr)>>1;
        build(v<<1,tl,tm);build(v<<1|1,tm+1,tr);
        t[v]=mg(t[v<<1],t[v<<1|1]);
    }
}
node get(int l,int r,int v,int tl,int tr){
    if(tl>=l&&tr<=r)
        return t[v];
    if(tl>r||tr<l)
        return emp;
    int tm=(tl+tr)>>1;
    return mg(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
}
vec<ll> minimum_costs(vec<int> a,vec<int> l,vec<int> r){
    int q=sz(l);
    vec<ll>ans(q);
    int n=sz(a);
    for(int i=0;i<n;i++) ::a[i]=a[i];
    bool ok=(*max_element(all(a))<=20);
    if(ok)
        build(1,0,n-1);
    vec<int>lft(n),rgt(n);
      vec<pii>st;
      st.pb({2e9,-1});
      for(int i=0;i<n;i++){
        while(sz(st) && a[i]>st.back().f){
            rgt[st.back().s]=i-1;
            st.pop_back();
        }
        lft[i]=st.back().s+1;
        st.pb({a[i],i});
      }
      while(sz(st)>1) rgt[st.back().s]=n-1,st.pop_back();
    const ll infq=1e18;
      auto stupid=[&](int l,int r){
            int mx=-2e9;
            vec<ll> pref(n+1,0);
            for(int i=l;i<=r;i++){
                int l1=i,r1=min(r,rgt[i]);
                ll cst=1ll*a[i]*(i-max(lft[i],l)+1);
                pref[l1]+=cst;pref[r1+1]-=cst;
    //            cout<<"ALO "<<l1<<' '<<r1<<' '<<cst<<endl;
                l1=max(l,lft[i]),r1=i;
                cst=1ll*a[i]*(min(rgt[i],r)-i+1);
    //            cout<<"ALO "<<l1<<' '<<r1<<' '<<cst<<endl;

                pref[l1]+=cst;pref[r1+1]-=cst;
                pref[i]-=a[i];pref[i+1]+=a[i];
            }
            for(int i=1;i<=n;i++) pref[i]+=pref[i-1];
            ll ans=infq;
            int j=l;
            int j1=l;
            for(int i=l;i<=r;i++){
                if(a[i]<a[j]) j=i;
                if(a[i]>a[j1]) j1=i;
                ans=min(ans,pref[i]);
    //            cerr<<"DBG "<<a[i]<<' '<<pref[i]<<'\n';
            }
    //        cout<<endl;
            return ans;
      };
    for(int i=0;i<q;i++){
        if(ok){
            ans[i]=inf;
            node me=get(l[i],r[i],1,0,n-1);
            for(auto &z : me.dpl) umin(ans[i],(ll)z);
            for(auto &z : me.dpr) umin(ans[i],(ll)z);
        }
        else
            ans[i]=stupid(l[i],r[i]);
    }
    return ans;
}

Compilation message

meetings.cpp: In lambda function:
meetings.cpp:109:17: warning: unused variable 'mx' [-Wunused-variable]
  109 |             int mx=-2e9;
      |                 ^~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 191172 KB Output is correct
2 Correct 144 ms 191348 KB Output is correct
3 Correct 213 ms 191416 KB Output is correct
4 Correct 141 ms 191340 KB Output is correct
5 Correct 140 ms 191388 KB Output is correct
6 Correct 147 ms 191428 KB Output is correct
7 Correct 189 ms 191300 KB Output is correct
8 Correct 159 ms 191296 KB Output is correct
9 Correct 150 ms 191300 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 191172 KB Output is correct
2 Correct 144 ms 191348 KB Output is correct
3 Correct 213 ms 191416 KB Output is correct
4 Correct 141 ms 191340 KB Output is correct
5 Correct 140 ms 191388 KB Output is correct
6 Correct 147 ms 191428 KB Output is correct
7 Correct 189 ms 191300 KB Output is correct
8 Correct 159 ms 191296 KB Output is correct
9 Correct 150 ms 191300 KB Output is correct
10 Correct 279 ms 191644 KB Output is correct
11 Correct 379 ms 191628 KB Output is correct
12 Correct 271 ms 191640 KB Output is correct
13 Correct 361 ms 191676 KB Output is correct
14 Correct 260 ms 191684 KB Output is correct
15 Correct 267 ms 191592 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 191220 KB Output is correct
2 Correct 940 ms 193360 KB Output is correct
3 Correct 2545 ms 198328 KB Output is correct
4 Correct 2605 ms 197636 KB Output is correct
5 Correct 1442 ms 198236 KB Output is correct
6 Correct 2193 ms 198208 KB Output is correct
7 Correct 2543 ms 198784 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 191220 KB Output is correct
2 Correct 940 ms 193360 KB Output is correct
3 Correct 2545 ms 198328 KB Output is correct
4 Correct 2605 ms 197636 KB Output is correct
5 Correct 1442 ms 198236 KB Output is correct
6 Correct 2193 ms 198208 KB Output is correct
7 Correct 2543 ms 198784 KB Output is correct
8 Correct 2744 ms 197700 KB Output is correct
9 Correct 2579 ms 197712 KB Output is correct
10 Correct 2297 ms 197716 KB Output is correct
11 Correct 2692 ms 197616 KB Output is correct
12 Correct 2568 ms 197628 KB Output is correct
13 Correct 2389 ms 197808 KB Output is correct
14 Correct 2442 ms 198208 KB Output is correct
15 Correct 2599 ms 197616 KB Output is correct
16 Correct 2418 ms 198232 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 191172 KB Output is correct
2 Correct 144 ms 191348 KB Output is correct
3 Correct 213 ms 191416 KB Output is correct
4 Correct 141 ms 191340 KB Output is correct
5 Correct 140 ms 191388 KB Output is correct
6 Correct 147 ms 191428 KB Output is correct
7 Correct 189 ms 191300 KB Output is correct
8 Correct 159 ms 191296 KB Output is correct
9 Correct 150 ms 191300 KB Output is correct
10 Correct 279 ms 191644 KB Output is correct
11 Correct 379 ms 191628 KB Output is correct
12 Correct 271 ms 191640 KB Output is correct
13 Correct 361 ms 191676 KB Output is correct
14 Correct 260 ms 191684 KB Output is correct
15 Correct 267 ms 191592 KB Output is correct
16 Correct 140 ms 191220 KB Output is correct
17 Correct 940 ms 193360 KB Output is correct
18 Correct 2545 ms 198328 KB Output is correct
19 Correct 2605 ms 197636 KB Output is correct
20 Correct 1442 ms 198236 KB Output is correct
21 Correct 2193 ms 198208 KB Output is correct
22 Correct 2543 ms 198784 KB Output is correct
23 Correct 2744 ms 197700 KB Output is correct
24 Correct 2579 ms 197712 KB Output is correct
25 Correct 2297 ms 197716 KB Output is correct
26 Correct 2692 ms 197616 KB Output is correct
27 Correct 2568 ms 197628 KB Output is correct
28 Correct 2389 ms 197808 KB Output is correct
29 Correct 2442 ms 198208 KB Output is correct
30 Correct 2599 ms 197616 KB Output is correct
31 Correct 2418 ms 198232 KB Output is correct
32 Execution timed out 5518 ms 245580 KB Time limit exceeded
33 Halted 0 ms 0 KB -