oj.uz

Submission #587478

# Submission time Handle Problem Language Result Execution time Memory
587478 2022-07-02T00:16:59 Z definitelynotmee Meetings (IOI18_meetings) C++17
60 / 100
 2314 ms 68856 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF = 1e9;

struct SegTree{
    struct seg{
        int val = 0, lz = 0;
    };
    vector<seg> tree;
    int sz, ql, qr, qval;
    SegTree(int n = 0){
        sz = n;
        tree = vector<seg>(4*n+1);
    }
    void refresh(int id, int l, int r){
        if(tree[id].lz == 0)
            return;
        if(l!=r){
            int e = id*2+1, d = id*2+2;
            tree[e].lz+=tree[id].lz;
            tree[d].lz+=tree[id].lz;
        }
        tree[id].val+=tree[id].lz;
        tree[id].lz = 0;
    }
    void update(int id, int l, int r){
        refresh(id,l,r);
        if(l > qr || r < ql)
            return;
        if(ql <= l && r <= qr){
            tree[id].lz+=qval;
            refresh(id,l,r);
            return;
        }
        int e = id*2+1, d = id*2+2, m = (l+r)>>1;
        update(e,l,m);
        update(d,m+1,r);
        tree[id] = {max(tree[e].val,tree[d].val),0};
    }

    int query(int id, int l, int r){
        refresh(id,l,r);
        if(l > qr || r < ql)
            return 0;
        if(ql <= l && r <= qr)
            return tree[id].val;
        int e = id*2+1, d = id*2+2, m = (l+r)>>1;
        return max(query(e,l,m),query(d,m+1,r));
    }

    void makeupd(int l, int r, int val){
        ql = l, qr = r, qval = val;
        update(0,0,sz-1);
    }

    int makeqry(int l, int r){
        ql = l, qr = r;
        return query(0,0,sz-1);
    }
};

struct upd{
    int l, r, val;
};


std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    int Q = L.size();
    int n = H.size();
    if(ll(n)*Q <= 1e8){
        vector<ll> resp(Q);
        vector<ll> val(n);

        for(int q = 0; q < Q; q++){
            fill(val.begin()+L[q],val.begin()+R[q]+1,0);
            ll cur = 0;
            vector<pll> st;
            for(int i = L[q]; i <= R[q]; i++){
                ll ct = 1;
                while(!st.empty() && st.back().ff <= H[i]){
                    cur-=st.back().ff*st.back().ss;
                    ct+=st.back().ss;
                    st.pop_back();
                }
                cur+=ct*H[i];
                st.push_back({H[i],ct});
                val[i]+=cur;
            }

            st.clear();
            cur = 0;

            for(int i = R[q]; i >= L[q]; i--){
                val[i]+=cur;

                ll ct = 1;
                while(!st.empty() && st.back().ff <= H[i]){
                    cur-=st.back().ff*st.back().ss;
                    ct+=st.back().ss;
                    st.pop_back();
                }
                cur+=ct*H[i];
                st.push_back({H[i],ct});
            }

            resp[q] = *min_element(val.begin()+L[q],val.begin()+R[q]+1);
        }
        return resp;
    }

    vector<ll> resp(Q);
    vector<int> o(Q);
    iota(all(o),0);
    sort(all(o),[&](int a, int b){
        return R[a] < R[b];
    });

    for(int & i : H)
        i--;
    
    int ptr = -1;

    array<vector<pii>,20> s;

    SegTree st(n);

    for(int q = 0; q < Q; q++){
        int l = L[o[q]], r = R[o[q]];
        while(r > ptr){
            ptr++;
            for(int i = 19; i > H[ptr]; i--){
                if(s[i].empty() || s[i].back().ff != ptr-1){
                    st.makeupd(ptr,ptr,1);
                    s[i].push_back({ptr,1});
                } else {
                    int sz = s[i].back().ss;
                    st.makeupd(ptr-sz,ptr-1,-sz);
                    sz++;
                    st.makeupd(ptr-sz+1,ptr,sz);
                    s[i].pop_back();
                    s[i].push_back({ptr,sz});
                }
            }
            // cout << "r = " << ptr << ":\n";
            // for(int i = 1; i < 5; i++){
            //     cout << i << " => ";
            //     for(pii j : s[i])
            //         cout << "(" << j.ff << ',' << j.ss << ") ";
            //     cout << '\n';
            // }
            // cout << "queries: ";
            // for(int i = 0; i <= ptr; i++)
            //     cout << st.makeqry(i,i) << ' ';
            // cout << '\n';
        }
        vector<upd> undo;
        undo.reserve(20);
        for(int i = 1; i < 20; i++){
            int id = lower_bound(all(s[i]),make_pair(l,0))-s[i].begin();
            if(id == s[i].size() || s[i][id].ff-s[i][id].ss+1 >= l)
                continue;
            //cout << "undo " << l << ' ' << r << ": " << i << ' ' << s[i][id].ff << ' ' << s[i][id].ss << '\n';
            int newsz = s[i][id].ff-l+1;
            st.makeupd(l,s[i][id].ff,newsz-s[i][id].ss);
            undo.push_back({l,s[i][id].ff,-(newsz-s[i][id].ss)});
        }
        resp[o[q]] = 20*(r-l+1)-st.makeqry(l,r);
        for(upd i : undo){
            //cout << "->"<< i.l << ' ' << i.r << ' ' << -i.val << '\n';
            st.makeupd(i.l,i.r,i.val);
        }
    }
    
    return resp;
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:170:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |             if(id == s[i].size() || s[i][id].ff-s[i][id].ss+1 >= l)
      |                ~~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 2 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 256 ms 596 KB Output is correct
11 Correct 749 ms 576 KB Output is correct
12 Correct 247 ms 596 KB Output is correct
13 Correct 753 ms 596 KB Output is correct
14 Correct 211 ms 596 KB Output is correct
15 Correct 200 ms 576 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 631 ms 1980 KB Output is correct
3 Correct 2119 ms 7448 KB Output is correct
4 Correct 2215 ms 6968 KB Output is correct
5 Correct 1499 ms 7344 KB Output is correct
6 Correct 1837 ms 6952 KB Output is correct
7 Correct 2133 ms 6956 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 631 ms 1980 KB Output is correct
3 Correct 2119 ms 7448 KB Output is correct
4 Correct 2215 ms 6968 KB Output is correct
5 Correct 1499 ms 7344 KB Output is correct
6 Correct 1837 ms 6952 KB Output is correct
7 Correct 2133 ms 6956 KB Output is correct
8 Correct 940 ms 10212 KB Output is correct
9 Correct 787 ms 10560 KB Output is correct
10 Correct 760 ms 10084 KB Output is correct
11 Correct 1052 ms 10216 KB Output is correct
12 Correct 913 ms 10204 KB Output is correct
13 Correct 855 ms 10100 KB Output is correct
14 Correct 374 ms 11636 KB Output is correct
15 Correct 2314 ms 8340 KB Output is correct
16 Correct 1623 ms 6952 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 256 ms 596 KB Output is correct
11 Correct 749 ms 576 KB Output is correct
12 Correct 247 ms 596 KB Output is correct
13 Correct 753 ms 596 KB Output is correct
14 Correct 211 ms 596 KB Output is correct
15 Correct 200 ms 576 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 631 ms 1980 KB Output is correct
18 Correct 2119 ms 7448 KB Output is correct
19 Correct 2215 ms 6968 KB Output is correct
20 Correct 1499 ms 7344 KB Output is correct
21 Correct 1837 ms 6952 KB Output is correct
22 Correct 2133 ms 6956 KB Output is correct
23 Correct 940 ms 10212 KB Output is correct
24 Correct 787 ms 10560 KB Output is correct
25 Correct 760 ms 10084 KB Output is correct
26 Correct 1052 ms 10216 KB Output is correct
27 Correct 913 ms 10204 KB Output is correct
28 Correct 855 ms 10100 KB Output is correct
29 Correct 374 ms 11636 KB Output is correct
30 Correct 2314 ms 8340 KB Output is correct
31 Correct 1623 ms 6952 KB Output is correct
32 Incorrect 866 ms 68856 KB Output isn't correct
33 Halted 0 ms 0 KB -