Submission #1074409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074409		TB_	Meetings (IOI18_meetings)	C++17	36 / 100	3891 ms	662256 KiB

meetings

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast,inline")

using namespace std;

#define ll long long
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define pb push_back
#define F first
#define S second
#define deb(x) cout << #x << " = " << (x) << endl 
#define deb2(x, y) cout << #x << " = " << (x)  << ", " << #y << " = " << (y) << endl 
typedef vector<ll> vl;
typedef vector<vl> vvl;

vl v;
vvl stdata(6000);
ll sufix = 0;

struct Node{
    Node *lnode, *rnode;
    ll l, r, val = 0, pref = 0, suf = 0;
    bool cover = 0;
    Node(ll l, ll r) : l(l), r(r){
        if(r-l==1) val=pref=suf=cover=v[l]; 
        else{
            ll mid =(r+l) / 2;
            lnode = new Node(l, mid);
            rnode = new Node(mid, r);
            val = max(lnode->val, rnode->val);
            val = max(val, lnode->suf+rnode->pref);
            pref = lnode->pref;
            suf = rnode->suf;
            cover=lnode->cover&rnode->cover;
            if(lnode->cover)pref+=rnode->pref;
            if(rnode->cover)suf+=lnode->suf;
        }
    }

    ll query(ll lo, ll hi){
        if(r <= lo || hi <= l) return 0;
        if(r <= hi && lo <= l){
            // deb2(l, r);
            ll ans = max(val, sufix+pref);
            if(cover)sufix+=suf;
            else sufix = suf;
            return ans;
        }
        return max(rnode->query(lo, hi), lnode->query(lo, hi));
    }
};
ll curr = 0;

void Node2(ll l, ll r, ll index = 1){
    while(stdata[curr].size()<=index) stdata[curr].pb(0);
    if(r-l==1) stdata[curr][index]=v[l]; 
    else{
        ll mid =(r+l) / 2;
        Node2(l, mid, index*2);
        Node2(mid, r, index*2+1);
        stdata[curr][index] = stdata[curr][index*2]+stdata[curr][index*2+1];
    }
}

ll query(ll lo, ll hi, ll l, ll r, ll index = 1){
    if(r <= lo || hi <= l) return 0;
    if(r <= hi && lo <= l){
        return stdata[curr][index];
    }
    ll mid = (l+r) / 2;
    return query(lo, hi, l, mid, index*2)+query(lo, hi, mid, r, index*2+1);
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int q = L.size();
    ll n = H.size();
    vl C;





    if(n>5000||q>5000){
        fo(i, n) v.pb(H[i] == 1);
        Node st(0, n+1);
        fo(i, q){
            sufix = 0;
            // deb(i);
            // deb(st.query(L[i], R[i]+1));
            C.pb((R[i]-L[i]+1)*2-st.query(L[i], R[i]+1));
        }

    }else{
        fo(meet, n){
            v.assign(n, 0);
            ll hi = H[meet];
            for(ll i = meet; i>=0; i--){
                hi = max(hi, (ll)H[i]);
                v[i] = hi;
            }
            hi = H[meet];
            for(ll i = meet; i<n; i++){
                hi = max(hi, (ll)H[i]);
                v[i] = hi;
            }
            // deb(meet);
            // fo(i, n) deb(v[i]);
            curr = meet;
            Node2(0, n);
        }
        fo(ind, q){
            ll best = 1e18;
            for(ll meet = L[ind]; meet<=R[ind]; meet++){
                curr = meet;
                best = min(best, query(L[ind], R[ind]+1, 0, n));
            }
            C.pb(best);
        }

    }
    // fo(i, q) deb(C[i]);
    return C;
}



// int main(){

//     // vector<int> a = {1, 1, 2, 1, 1, 1, 2, 2, 1};
//     // vector<int> b = {0, 2};
//     // vector<int> c = {5, 5};
//     vector<int> a = {2, 4, 3, 5};
//     vector<int> b = {0, 1};
//     vector<int> c = {2, 3};
//     minimum_costs(a, b, c);
//     return 0;
// }

Compilation message (stderr)

meetings.cpp: In function 'void Node2(long long int, long long int, long long int)':
meetings.cpp:56:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   56 |     while(stdata[curr].size()<=index) stdata[curr].pb(0);
      |           ~~~~~~~~~~~~~~~~~~~^~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40