Submission #1133548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133548		HuyAT	Holiday (IOI14_holiday)	C++17	Compilation error	0 ms	0 KiB

holiday

#include<bits/stdc++.h>
#define newl '\n'
#include<holiday.h>

const int N = 1e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;

struct Node{
    Node *l,*r;
    long long val,cnt;
    Node(long long val,long long cnt) : l(nullptr),r(nullptr),val(val),cnt(cnt){

    }
    Node(Node *ll,Node *rr){
        assert(ll && rr);
        l = ll;
        r = rr;
        val = l->val + r->val;
        cnt = l->cnt + r->cnt;
    }
};
typedef Node* pNode;

struct PersistentST{
    std::vector<pNode> root;
    PersistentST(){
        root.emplace_back(new Node(0LL,0LL));
        root.back()->l = root.back();
        root.back()->r = root.back();
    }
    pNode update(int l,int r,int pos,int val,pNode t){
        if(l == r){
            return new Node(val,1);
        }
        int mid = (l + r) / 2;
        if(pos <= mid){
            return new Node(update(l,mid,pos,val,t->l),t->r);
        }
        return new Node(t->l,update(mid + 1,r,pos,val,t->r));
    }
    long long query(int l,int r,int val,pNode t){
        if(l == r){
            return t->val;
        }
        int mid = (l + r) / 2;
        if(val <= t->l->cnt){
            return query(l,mid,val,t->l);
        }
        return t->l->val + query(mid + 1,r,val - t->l->cnt,t->r);
    }
public:
    long long query(int l,int r,int pos,int ver){
        return query(l,r,pos,root[ver]);
    }
    void update(int l,int r,int pos,int val,int ver){
        root.emplace_back(update(l,r,pos,val,root[ver]));
    }
};


std::vector<long long> optimal(const std::vector<int> &a){
    int n = (int)a.size() - 1;
    std::vector<int> id(n + 1,0);
    std::vector<long long> ans(1,0);
    auto compress = [&](){
        std::map<int,int> m;
        for(int i = 1;i <= n;++i){
            ++m[a[i]];
        }
        std::map<int,int>::iterator it;
        for(it = m.end();it != m.begin();it = prev(it)){
            if(it != m.end() && next(it) != m.end()){
                it->second += next(it)->second;
            }
        }
        if((int)m.size() > 1){
            it->second += next(it)->second;
        }
        for(int i = n;i >= 1;--i){
    //        std::cout << "IMP " << i << " " << m[a[i]] << newl;
            id[i] = m[a[i]]--;
        }
    };
    compress();
    std::set<int> s;
    std::map<int,int> m;
    PersistentST st;
    auto eval = [&](int ver,int opt) -> long long{
        if(ver > opt){
            return -INF;
        }
        return st.query(1,n,opt - (ver - 1),ver);
    };
    auto get = [&](int opt) -> long long{
//        assert(!s.empty());
        int x = *prev(s.upper_bound(opt));
        int ver = m[x];
        assert(opt >= ver);
        return eval(ver,opt);
    };
    auto dominate = [&](int cur) -> void{
        while(!s.empty()){
            int x = *s.rbegin();
//                std::cerr << eval(m[x],x) << " " << eval(cur,x) << newl;
            if(eval(m[x],x) <= eval(cur,x)){
                s.erase(x);
                m.erase(x);
            }else{
                break;
            }
        }
        if(s.empty()){
            s.insert(1);
            m[1] = cur;
            return;
        }
        int prev = m[*s.rbegin()];
        int lo = *s.rbegin() + 1,hi = n * 2,ans = n * 2;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(eval(prev,mid) < eval(cur,mid)){
                hi = mid - 1;
                ans = mid;
            }else{
                lo = mid + 1;
            }
        }
        s.insert(ans);
        m[ans] = cur;
//        auto dfs = [&](auto dfs, int u, int p) -> void{
//            for(int v : adj[u]){
//                if(v == p) continue;
//                dfs(dfs, v, u);
//            }
//        }
    };
    for(int i = 1;i <= n;++i){
        st.update(1,n,id[i],a[i],i - 1);
        dominate(i);
    }
//    return ans;
    for(int i = 1;i <= n * 2;++i){
        ans.emplace_back(get(i));
//        std::cout << ans.back() << " ";
    }
//    std::cout << newl;
    return ans;
}
long long solve(const std::vector<int> &a,int s,int k){
    int n = (int)a.size() - 1;
    long long ans = 0;
//    return 0;
    std::vector<int> left(2,0),right(1,0);
    for(int i = s;i <= n;++i){
        right.emplace_back(a[i]);
    }
    for(int i = s - 1;i >= 1;--i){
        left.emplace_back(0);
        left.emplace_back(a[i]);
    }
//    std::cerr << "LEFT\n";
    std::vector<long long> f = optimal(left);
//    std::cerr << "RIGHT\n";
    std::vector<long long> f1 = optimal(right);
//    return 0;
    for(int i = 0;i < std::min((int)f1.size(),k + 1);++i){
        int it = std::max(0,std::min((int)f.size() - 1,k - i));
        ans = std::max(ans,f[it] + f1[i]);
    }
    return ans;
}
long long int findMaxAttraction(int n,int start,int d,int attraction[]){
    long long ans = 0;
    ++start;
    std::vector<int> a(n + 1,0);
    for(int i = 1;i <= n;++i){
        a[i] = attraction[i - 1];
    }
    ans = std::max(ans,solve(a,start,d));
    std::reverse(a.begin() + 1,a.end());
    start = n - start + 1;
    ans = std::max(ans,solve(a,start,d));
    return ans;
}
//int main(){
//    std::ios_base::sync_with_stdio(false);
//    std::cin.tie(nullptr);std::cout.tie(nullptr);
//
//    return 0;
//}

Compilation message (stderr)

holiday.cpp:3:9: fatal error: holiday.h: No such file or directory
    3 | #include<holiday.h>
      |         ^~~~~~~~~~~
compilation terminated.