oj.uz

Submission #418045

# Submission time Handle Problem Language Result Execution time Memory
418045 2021-06-04T23:42:52 Z duality Meetings (IOI18_meetings) C++11
100 / 100
 3206 ms 277560 KB 
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#include "meetings.h"
#pragma GCC optimize("Ofast")

int N,h[750000],sparse[750000][20];
int logg[750001];
int rev = 0;
int query(int s,int e) {
    if (rev) {
        s = N-1-s,e = N-1-e,swap(s,e);
        int l = logg[e-s+1];
        return (h[N-sparse[s][l]-1] > h[N-sparse[e-(1 << l)+1][l]-1]) ? N-sparse[s][l]-1:N-sparse[e-(1 << l)+1][l]-1;
    }
    else {
        int l = logg[e-s+1];
        return (h[sparse[s][l]] > h[sparse[e-(1 << l)+1][l]]) ? sparse[s][l]:sparse[e-(1 << l)+1][l];
    }
}
vector<pair<pii,int> > qq[750000];
LLI ans[750000];
LLI tree[1 << 21],lazyb[1 << 21];
int lazym[1 << 21];
int build(int s,int e,int i) {
    if (s == e) {
        tree[i] = lazym[i] = lazyb[i] = 0;
        return 0;
    }

    int mid = (s+e) / 2;
    build(s,mid,2*i+1),build(mid+1,e,2*i+2);
    tree[i] = lazym[i] = lazyb[i] = 0;
    return 0;
}
int prop(int s,int e,int i) {
    if (lazym[i] != 0) {
        tree[i] = (LLI) lazym[i]*(e-s)+lazyb[i];
        if (s != e) {
            int mid = (s+e) / 2;
            lazym[2*i+1] = lazym[2*i+2] = lazym[i];
            lazyb[2*i+1] = lazyb[i],lazyb[2*i+2] = (LLI) lazym[i]*(mid+1-s)+lazyb[i];
        }
        lazym[i] = lazyb[i] = 0;
    }
    else if (lazyb[i] != 0) {
        tree[i] += lazyb[i];
        if (s != e) lazyb[2*i+1] += lazyb[i],lazyb[2*i+2] += lazyb[i];
        lazyb[i] = 0;
    }
    return 0;
}
int update(int s,int e,int as,int ae,int i,int m,LLI b) {
    prop(s,e,i);
    if ((s > ae) || (e < as)) return 0;
    else if ((s >= as) && (e <= ae)) {
        lazym[i] = m,lazyb[i] = (LLI) m*(s-as)+b;
        prop(s,e,i);
        return 0;
    }

    int mid = (s+e) / 2;
    update(s,mid,as,ae,2*i+1,m,b),update(mid+1,e,as,ae,2*i+2,m,b);
    tree[i] = tree[2*i+2];
    return 0;
}
LLI query(int s,int e,int q,int i) {
    prop(s,e,i);
    if (q == e) return tree[i];

    int mid = (s+e) / 2;
    if (q <= mid) return query(s,mid,q,2*i+1);
    else return query(mid+1,e,q,2*i+2);
}
int query2(int s,int e,int qs,int qe,int i,LLI q) {
    prop(s,e,i);
    if ((s > qe) || (e < qs)) return -1;
    else if ((e <= qe) && (tree[i] < q+(LLI) h[qe]*(qe-e+1))) return -1;
    else if ((s >= qs) && (e <= qe)) {
        while (s != e) {
            int mid = (s+e) / 2;
            prop(s,mid,2*i+1);
            if (tree[2*i+1] >= q+(LLI) h[qe]*(qe-mid+1)) e = mid,i = 2*i+1;
            else prop(mid+1,e,2*i+2),s = mid+1,i = 2*i+2;
        }
        return s;
    }

    int mid = (s+e) / 2;
    int r = query2(s,mid,qs,qe,2*i+1,q);
    if (r != -1) return r;
    else return query2(mid+1,e,qs,qe,2*i+2,q);
}
LLI solve(int s,int e) {
    if (s > e) return 0;
    int i;
    int m = query(s,e);
    LLI a = solve(s,m-1),b = solve(m+1,e);
    vector<pair<pii,int> > &v = rev ? qq[N-m-1]:qq[m];
    for (i = 0; i < v.size(); i++) {
        pii p = rev ? mp(N-v[i].first.second-1,N-v[i].first.first-1):v[i].first;
        ans[v[i].second] = min(ans[v[i].second],query(0,N-1,p.first,0)+(LLI) h[m]*(p.second-m+1));
    }
    int p;
    a += (LLI) h[m]*(e-m+1);
    if (a < b+(LLI) h[m]*(m-s+1)) {
        p = query2(0,N-1,s,m,0,b-(LLI) h[m]*(e-m+1));
        update(0,N-1,s,p-1,0,0,(LLI) h[m]*(e-m+1));
    }
    else a = b+(LLI) h[m]*(m-s+1),p = s;
    update(0,N-1,p,m,0,-h[m],b+(LLI) h[m]*(m-p+1));
    return a;
}
vector<long long int> minimum_costs(vector<int> H,vector<int> L,vector<int> R) {
    int i,j,Q = L.size();
    N = H.size();
    for (i = 0; i < N; i++) h[i] = H[i],sparse[i][0] = i;
    for (i = 1; (1 << i) <= N; i++) {
        for (j = 0; j <= N-(1 << i); j++) sparse[j][i] = (h[sparse[j][i-1]] > h[sparse[j+(1 << (i-1))][i-1]]) ? sparse[j][i-1]:sparse[j+(1 << (i-1))][i-1];
    }
    for (i = 2; i <= N; i++) logg[i] = logg[i/2]+1;
    for (i = 0; i < Q; i++) qq[query(L[i],R[i])].pb(mp(mp(L[i],R[i]),i)),ans[i] = 1e18;
    solve(0,N-1),reverse(h,h+N),rev = 1;
    build(0,N-1,0),solve(0,N-1);
    return vector<LLI>(ans,ans+Q);
}

Compilation message

meetings.cpp: In function 'LLI solve(int, int)':
meetings.cpp:153:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (i = 0; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17868 KB Output is correct
2 Correct 13 ms 18408 KB Output is correct
3 Correct 13 ms 18380 KB Output is correct
4 Correct 13 ms 18396 KB Output is correct
5 Correct 13 ms 18316 KB Output is correct
6 Correct 13 ms 18636 KB Output is correct
7 Correct 13 ms 18316 KB Output is correct
8 Correct 13 ms 18636 KB Output is correct
9 Correct 13 ms 18440 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17868 KB Output is correct
2 Correct 13 ms 18408 KB Output is correct
3 Correct 13 ms 18380 KB Output is correct
4 Correct 13 ms 18396 KB Output is correct
5 Correct 13 ms 18316 KB Output is correct
6 Correct 13 ms 18636 KB Output is correct
7 Correct 13 ms 18316 KB Output is correct
8 Correct 13 ms 18636 KB Output is correct
9 Correct 13 ms 18440 KB Output is correct
10 Correct 19 ms 19076 KB Output is correct
11 Correct 19 ms 19192 KB Output is correct
12 Correct 20 ms 19052 KB Output is correct
13 Correct 18 ms 19080 KB Output is correct
14 Correct 19 ms 19492 KB Output is correct
15 Correct 17 ms 19152 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17868 KB Output is correct
2 Correct 50 ms 22792 KB Output is correct
3 Correct 249 ms 46392 KB Output is correct
4 Correct 201 ms 39200 KB Output is correct
5 Correct 260 ms 47456 KB Output is correct
6 Correct 261 ms 48140 KB Output is correct
7 Correct 257 ms 49828 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17868 KB Output is correct
2 Correct 50 ms 22792 KB Output is correct
3 Correct 249 ms 46392 KB Output is correct
4 Correct 201 ms 39200 KB Output is correct
5 Correct 260 ms 47456 KB Output is correct
6 Correct 261 ms 48140 KB Output is correct
7 Correct 257 ms 49828 KB Output is correct
8 Correct 244 ms 39748 KB Output is correct
9 Correct 205 ms 39472 KB Output is correct
10 Correct 229 ms 39852 KB Output is correct
11 Correct 233 ms 39148 KB Output is correct
12 Correct 203 ms 38864 KB Output is correct
13 Correct 239 ms 39520 KB Output is correct
14 Correct 259 ms 46404 KB Output is correct
15 Correct 194 ms 38912 KB Output is correct
16 Correct 288 ms 46504 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17868 KB Output is correct
2 Correct 13 ms 18408 KB Output is correct
3 Correct 13 ms 18380 KB Output is correct
4 Correct 13 ms 18396 KB Output is correct
5 Correct 13 ms 18316 KB Output is correct
6 Correct 13 ms 18636 KB Output is correct
7 Correct 13 ms 18316 KB Output is correct
8 Correct 13 ms 18636 KB Output is correct
9 Correct 13 ms 18440 KB Output is correct
10 Correct 19 ms 19076 KB Output is correct
11 Correct 19 ms 19192 KB Output is correct
12 Correct 20 ms 19052 KB Output is correct
13 Correct 18 ms 19080 KB Output is correct
14 Correct 19 ms 19492 KB Output is correct
15 Correct 17 ms 19152 KB Output is correct
16 Correct 11 ms 17868 KB Output is correct
17 Correct 50 ms 22792 KB Output is correct
18 Correct 249 ms 46392 KB Output is correct
19 Correct 201 ms 39200 KB Output is correct
20 Correct 260 ms 47456 KB Output is correct
21 Correct 261 ms 48140 KB Output is correct
22 Correct 257 ms 49828 KB Output is correct
23 Correct 244 ms 39748 KB Output is correct
24 Correct 205 ms 39472 KB Output is correct
25 Correct 229 ms 39852 KB Output is correct
26 Correct 233 ms 39148 KB Output is correct
27 Correct 203 ms 38864 KB Output is correct
28 Correct 239 ms 39520 KB Output is correct
29 Correct 259 ms 46404 KB Output is correct
30 Correct 194 ms 38912 KB Output is correct
31 Correct 288 ms 46504 KB Output is correct
32 Correct 2225 ms 166100 KB Output is correct
33 Correct 1718 ms 165024 KB Output is correct
34 Correct 2057 ms 169368 KB Output is correct
35 Correct 2247 ms 169056 KB Output is correct
36 Correct 1716 ms 166984 KB Output is correct
37 Correct 2057 ms 169684 KB Output is correct
38 Correct 2548 ms 224172 KB Output is correct
39 Correct 2684 ms 223940 KB Output is correct
40 Correct 2550 ms 176668 KB Output is correct
41 Correct 2993 ms 275104 KB Output is correct
42 Correct 3203 ms 277560 KB Output is correct
43 Correct 3206 ms 277380 KB Output is correct
44 Correct 2829 ms 223712 KB Output is correct