oj.uz

Submission #891646

# Submission time Handle Problem Language Result Execution time Memory
891646 2023-12-23T12:51:49 Z vjudge1 Meetings (IOI18_meetings) C++17
36 / 100
 693 ms 18072 KB 
#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

vll solve(vector<int> V, int delta, int len) {
    stack<int> S;
    vll re;
    ll cur = 0;
    for(int i = 0; i < len; ++i) {
        while(!S.empty() && V[i + delta] > V[S.top() + delta]) {
            int p = S.top();
            S.pop();
            int p2 = 0;
            if(!S.empty()) p2 = S.top() + 1;
            cur -= 1ll * (p - p2 + 1) * V[p + delta];
        }
        int p = 0;
        if(!S.empty()) p = S.top() + 1;
        cur += 1ll * (i - p + 1) * V[i + delta];
        S.push(i);
        re.push_back(cur);
    }
    return re;
}

using ii = pair<int, int>;

struct banda {
    bool mono;
    int len;

    int vma = 0;

    ii st, dr; /// perechi (val, len)
    
    banda(int l = 0, int cul = 0) {
        mono = 1;
        len = l;
        st = dr = {cul, l};
        if(cul == 1) vma = l;
    }
    banda operator+(banda rhs) {
        banda re;
        if(mono && rhs.mono && st.first == rhs.st.first) {
            re = banda(len + rhs.len, st.first);
            return re;
        }
        
        re.vma = max(vma, rhs.vma);
        re.st = st;
        re.dr = rhs.dr;
        if(mono && rhs.st.first == st.first) {
            re.st.second += rhs.st.second;
        }

        if(dr.first == 1 && rhs.st.first == 1)
            re.vma = max(re.vma, dr.second + rhs.st.second);

        if(rhs.mono && dr.first == rhs.st.first)
            re.dr.second += dr.second;
        
        if(re.st.first == 1)
            re.vma = max(re.vma, re.st.second);
        if(re.dr.first == 1)
            re.vma = max(re.vma, re.dr.second);
        re.mono = 0;

        return re;
    }

};

struct AINT {
    vector<banda> V;
    int n;
    AINT(int N) : n(N), V(4 * N) {}

    void update(int u, int v) { update(u, v, 1, 0, n - 1); }

    void update(int p, int v, int u, int s, int d) {
        if(d < p || p < s) return;
        if(s == d) {
           V[u] = banda(1, v); 
           return;
        }
        update(p, v, u << 1, s, (s + d) >> 1);
        update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u] = V[u << 1] + V[u << 1 | 1];
    }

    banda query(int l, int r) { return query(l, r, 1, 0, n - 1); }

    banda query(int l, int r, int u, int s, int d) {
        int m = (s + d) >> 1;
        if(l <= s && d <= r) return V[u];
        if(r <= m) return query(l, r, u << 1, s, m);
        if(m < l) return query(l, r, u << 1 | 1, m + 1, d);
        return query(l, r, u << 1, s, m) + query(l, r, u << 1 | 1, m + 1, d);
    }
};

vll minimum_costs(vi H, vi L, vi R) {
    vector<int> S(H);
    vi RH = H;
    reverse(RH.begin(), RH.end());
    vi RS(RH);
    int n = H.size();
    vll RE;
    if(H.size() <= 5000 && L.size() <= 5000) {
        for(int q = 0; q < L.size(); ++q) {
            vll opt1 = solve(S, L[q], R[q] - L[q] + 1);
            vll opt2 = solve(RS, n - 1 - R[q], R[q] - L[q] + 1);
            reverse(opt2.begin(), opt2.end());
            ll re = opt1[0] + opt2[0];
            for(int i = 0; i < R[q] - L[q] + 1; i++)
                re = min(re, opt1[i] + opt2[i] - H[i + L[q]]);
            RE.push_back(re);
        }
        return RE;
    }
    ///sper ca 0 sau 1;
    AINT A(n);
    for(int i = 0; i < n; ++i)
        A.update(i, H[i]);
    vll Re;
    int q = L.size();
    for(int i = 0; i < q; ++i) {
        int v = A.query(L[i], R[i]).vma;
        Re.push_back((R[i] - L[i] + 1) * 2 - v);
        // cout << v << " ";
    }
//    cout << "\n\n";
    return Re;
}

Compilation message

meetings.cpp: In constructor 'AINT::AINT(int)':
meetings.cpp:80:9: warning: 'AINT::n' will be initialized after [-Wreorder]
   80 |     int n;
      |         ^
meetings.cpp:79:19: warning:   'std::vector<banda> AINT::V' [-Wreorder]
   79 |     vector<banda> V;
      |                   ^
meetings.cpp:81:5: warning:   when initialized here [-Wreorder]
   81 |     AINT(int N) : n(N), V(4 * N) {}
      |     ^~~~
meetings.cpp: In function 'vll minimum_costs(vi, vi, vi)':
meetings.cpp:115:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for(int q = 0; q < L.size(); ++q) {
      |                        ~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 213 ms 1040 KB Output is correct
11 Correct 693 ms 880 KB Output is correct
12 Correct 191 ms 772 KB Output is correct
13 Correct 682 ms 1116 KB Output is correct
14 Correct 92 ms 836 KB Output is correct
15 Correct 110 ms 1056 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 29 ms 2768 KB Output is correct
3 Correct 101 ms 17864 KB Output is correct
4 Correct 92 ms 17980 KB Output is correct
5 Correct 67 ms 18072 KB Output is correct
6 Correct 83 ms 18056 KB Output is correct
7 Correct 92 ms 18068 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 29 ms 2768 KB Output is correct
3 Correct 101 ms 17864 KB Output is correct
4 Correct 92 ms 17980 KB Output is correct
5 Correct 67 ms 18072 KB Output is correct
6 Correct 83 ms 18056 KB Output is correct
7 Correct 92 ms 18068 KB Output is correct
8 Incorrect 91 ms 17976 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 213 ms 1040 KB Output is correct
11 Correct 693 ms 880 KB Output is correct
12 Correct 191 ms 772 KB Output is correct
13 Correct 682 ms 1116 KB Output is correct
14 Correct 92 ms 836 KB Output is correct
15 Correct 110 ms 1056 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 29 ms 2768 KB Output is correct
18 Correct 101 ms 17864 KB Output is correct
19 Correct 92 ms 17980 KB Output is correct
20 Correct 67 ms 18072 KB Output is correct
21 Correct 83 ms 18056 KB Output is correct
22 Correct 92 ms 18068 KB Output is correct
23 Incorrect 91 ms 17976 KB Output isn't correct
24 Halted 0 ms 0 KB -