oj.uz

답안 #900855

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
900855 2024-01-09T04:38:49 Z abcvuitunggio 모임들 (IOI18_meetings) C++17
100 / 100
 2406 ms 292092 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
struct line{
    long long a,b;
}a[750001];
vector <int> ql,qr,ve[750001],v;
vector <long long> h,res,ans;
set <int> s;
int n,q,mx[750001][20],lg[750001];
int f(int l, int r){
    int d=lg[r-l+1],x=mx[l][d],y=mx[r-(1<<d)+1][d];
    return (h[x]<h[y]?y:x);
}
long long calc(int i){
    int j=*s.lower_bound(i);
    return a[j].a*i+a[j].b;
}
long long dnc(int l, int r){
    if (l>r)
        return 0;
    if (l==r){
        a[l]={h[l],h[l]*(1-l)};
        s.insert(l);
        for (int i:ve[l])
            if (qr[i]<=r)
                ans[i]+=h[l];
        return 0;
    }
    int mid=f(l,r);
    long long x=dnc(l,mid-1),y=dnc(mid+1,r)+h[mid]*(mid-l+1),c=(mid>l?calc(mid-1):0)+x+h[mid];
    v.clear();
    v.push_back(mid);
    s.insert(mid);
    int last=mid;
    for (auto it=s.upper_bound(mid);it!=s.end()&&*it<=r;it++){
        int i=*it;
        if (h[mid]*i+c-h[mid]*mid<=a[i].a*i+a[i].b+y){
            v.push_back(i);
            last=i;
            continue;
        }
        last=(a[i].b+y-c+h[mid]*mid)/(h[mid]-a[i].a);
        break;
    }
    for (int i:v)
        s.erase(i);
    s.insert(last);
    a[last]={h[mid],c-h[mid]*mid-y};
    if (mid-l<r-mid+1){
        for (int i=l;i<mid;i++)
            a[i].b+=x-y;
        for (int i:ve[l])
            if (qr[i]>=mid&&qr[i]<=r)
                ans[i]+=calc(qr[i])+y;
        return y;
    }
    for (int i=mid;i<=r;i++)
        a[i].b+=y-x;
    for (int i:ve[l])
        if (qr[i]>=mid&&qr[i]<=r)
            ans[i]+=calc(qr[i])+x;
    return x;
}
void solve(){
    s.clear();
    for (int j=1;j<20;j++)
        for (int i=0;i+(1<<j)-1<n;i++){
            int l=mx[i][j-1],r=mx[i+(1<<(j-1))][j-1];
            mx[i][j]=(h[l]<h[r]?r:l);
        }
    for (int i=0;i<n;i++)
        ve[i].clear();
    for (int i=0;i<q;i++){
        int v=f(ql[i],qr[i]);
        ans[i]=h[v]*(v-ql[i]+1);
        if (v<qr[i])
            ve[v+1].push_back(i);
    }
    dnc(0,n-1);
    for (int i=0;i<q;i++)
        res[i]=min(res[i],ans[i]);
}
vector <long long> minimum_costs(vector <int> H, vector <int> L, vector <int> R){
    ql=L,qr=R,n=H.size(),q=L.size();
    for (int i:H)
        h.push_back(i);
    res.assign(q,1e18);
    for (int i=2;i<=n;i++)
        lg[i]=lg[i/2]+1;
    for (int i=0;i<n;i++)
        mx[i][0]=i;
    ans.assign(q,0);
    solve();
    reverse(h.begin(),h.end());
    for (int i=0;i<q;i++){
        ql[i]=n-ql[i]-1;
        qr[i]=n-qr[i]-1;
        swap(ql[i],qr[i]);
    }
    solve();
    return res;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 6 ms 22996 KB Output is correct
3 Correct 8 ms 22876 KB Output is correct
4 Correct 6 ms 22876 KB Output is correct
5 Correct 6 ms 22872 KB Output is correct
6 Correct 6 ms 23252 KB Output is correct
7 Correct 8 ms 22876 KB Output is correct
8 Correct 5 ms 23132 KB Output is correct
9 Correct 5 ms 23132 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 6 ms 22996 KB Output is correct
3 Correct 8 ms 22876 KB Output is correct
4 Correct 6 ms 22876 KB Output is correct
5 Correct 6 ms 22872 KB Output is correct
6 Correct 6 ms 23252 KB Output is correct
7 Correct 8 ms 22876 KB Output is correct
8 Correct 5 ms 23132 KB Output is correct
9 Correct 5 ms 23132 KB Output is correct
10 Correct 9 ms 23384 KB Output is correct
11 Correct 10 ms 23384 KB Output is correct
12 Correct 9 ms 23392 KB Output is correct
13 Correct 9 ms 23388 KB Output is correct
14 Correct 11 ms 23896 KB Output is correct
15 Correct 9 ms 23388 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 27 ms 26576 KB Output is correct
3 Correct 164 ms 51808 KB Output is correct
4 Correct 92 ms 42952 KB Output is correct
5 Correct 103 ms 49892 KB Output is correct
6 Correct 125 ms 52676 KB Output is correct
7 Correct 95 ms 54376 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 27 ms 26576 KB Output is correct
3 Correct 164 ms 51808 KB Output is correct
4 Correct 92 ms 42952 KB Output is correct
5 Correct 103 ms 49892 KB Output is correct
6 Correct 125 ms 52676 KB Output is correct
7 Correct 95 ms 54376 KB Output is correct
8 Correct 135 ms 45252 KB Output is correct
9 Correct 116 ms 45000 KB Output is correct
10 Correct 129 ms 45256 KB Output is correct
11 Correct 127 ms 43128 KB Output is correct
12 Correct 116 ms 42668 KB Output is correct
13 Correct 113 ms 43204 KB Output is correct
14 Correct 144 ms 52872 KB Output is correct
15 Correct 80 ms 43148 KB Output is correct
16 Correct 97 ms 50880 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 6 ms 22996 KB Output is correct
3 Correct 8 ms 22876 KB Output is correct
4 Correct 6 ms 22876 KB Output is correct
5 Correct 6 ms 22872 KB Output is correct
6 Correct 6 ms 23252 KB Output is correct
7 Correct 8 ms 22876 KB Output is correct
8 Correct 5 ms 23132 KB Output is correct
9 Correct 5 ms 23132 KB Output is correct
10 Correct 9 ms 23384 KB Output is correct
11 Correct 10 ms 23384 KB Output is correct
12 Correct 9 ms 23392 KB Output is correct
13 Correct 9 ms 23388 KB Output is correct
14 Correct 11 ms 23896 KB Output is correct
15 Correct 9 ms 23388 KB Output is correct
16 Correct 5 ms 22876 KB Output is correct
17 Correct 27 ms 26576 KB Output is correct
18 Correct 164 ms 51808 KB Output is correct
19 Correct 92 ms 42952 KB Output is correct
20 Correct 103 ms 49892 KB Output is correct
21 Correct 125 ms 52676 KB Output is correct
22 Correct 95 ms 54376 KB Output is correct
23 Correct 135 ms 45252 KB Output is correct
24 Correct 116 ms 45000 KB Output is correct
25 Correct 129 ms 45256 KB Output is correct
26 Correct 127 ms 43128 KB Output is correct
27 Correct 116 ms 42668 KB Output is correct
28 Correct 113 ms 43204 KB Output is correct
29 Correct 144 ms 52872 KB Output is correct
30 Correct 80 ms 43148 KB Output is correct
31 Correct 97 ms 50880 KB Output is correct
32 Correct 1020 ms 150096 KB Output is correct
33 Correct 855 ms 156888 KB Output is correct
34 Correct 1305 ms 151032 KB Output is correct
35 Correct 1344 ms 152800 KB Output is correct
36 Correct 1016 ms 151772 KB Output is correct
37 Correct 1223 ms 152276 KB Output is correct
38 Correct 2044 ms 225572 KB Output is correct
39 Correct 2406 ms 233440 KB Output is correct
40 Correct 1788 ms 179852 KB Output is correct
41 Correct 1852 ms 291032 KB Output is correct
42 Correct 2035 ms 290804 KB Output is correct
43 Correct 2146 ms 292092 KB Output is correct
44 Correct 1995 ms 220156 KB Output is correct