Submission #794722

#	Time	Username	Problem	Language	Result	Execution time	Memory
794722		merlin	모임들 (IOI18_meetings)	C++14	0 / 100	58 ms	2808 KiB

meetings

#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define ll long long
#define f first
#define s second

void setIO(string name="") {
	cin.tie(0)->sync_with_stdio(0);
	if (!name.empty()) {
		freopen((name+".in").c_str(), "r", stdin);
		freopen((name+".out").c_str(), "w", stdout);
	}
}

struct Tree{
    int n=1;
    vector<int> vals,l_vals,r_vals,left,right;
    vector<int> combine(vector<int> a,vector<int> b){ //val, left, right
        vector<int> ans = {max(a[0],max(a[2] + b[1],b[0])),a[1],b[2],0};
        if(a[3]) ans[1] = a[0] + b[1];
        if(b[3]) ans[2] = a[1] + b[0];
        if(a[3] && b[3]) ans[3] = 1;
        return ans;
    }
    Tree(int sz,vector<int> &v){
        while(n < sz)n*=2;
        vals = l_vals = r_vals = left = right = vector<int>(2*n,0);
        for(int i = 0;i<n;i++){
            left[i+n] = i;
            right[i+n] = i+1;
            if(i < sz){
                vals[i+n] = v[i] == 1 ? 1 : 0;
                l_vals[i+n] = v[i] == 1 ? 1 : 0;
                r_vals[i+n] = v[i] == 1 ? 1 : 0;
            }
        }
        for(int i = n-1;i;i--){
            left[i] = left[i*2];
            right[i] = right[i*2+1];
            vector<int> tmp = combine({vals[i*2],l_vals[i*2],r_vals[i*2],vals[i*2] == right[i*2] - left[i*2]},{vals[i*2+1],l_vals[i*2+1],r_vals[i*2+1],vals[i*2+1] == right[i*2 + 1] - left[i*2+1]});
            vals[i] = tmp[0];
            l_vals[i] = tmp[1];
            r_vals[i] = tmp[2];
        }
    }
    int range_query(int l,int r){
        //cerr<<"wtfff "<<l<<" "<<r<<endl;
        vector<int> tmp = range_query(l,r,1);
        return tmp[0];
    }
    vector<int> range_query(int l,int r,int cur){
        //cerr<<cur<<" "<<l<<" "<<r<<" "<<left[cur]<<" "<<right[cur]<<" ";
        if(l >= right[cur] || r <= left[cur]){
            //cerr<<"mimo"<<endl;
            return {0,0,0};
        }
        if(l <= left[cur] && r >= right[cur]){
            //cerr<<"cely in"<<endl;
            return {vals[cur],l_vals[cur],r_vals[cur],vals[cur] == right[cur] - left[cur]};
        }
        //cerr<<"divne"<<endl;
        return combine(range_query(l,r,cur*2),range_query(l,r,cur*2+1));
    }
};

vector<ll> minimum_costs(vector<int> H,vector<int> L,vector<int> R){
    int q = L.size(),n = H.size();
    if(0 && n <= 3000 && q <= 10){
        vector<ll> anss;
        for(int Q = 0;Q<q;Q++){
            ll ans = 1e16;
            for(int i = L[Q];i<=R[Q];i++){
                ll tmp = H[i];
                ll mx = H[i];
                for(int j = i+1;j <= R[Q];j++){
                    mx = max(mx,(ll)H[j]);
                    tmp += mx;
                }
                mx = H[i];
                for(int j = i-1;j >= L[Q];j--){
                    mx = max(mx,(ll)H[j]);
                    tmp += mx;
                }
                ans = min(ans,tmp);
            }
            anss.push_back(ans);
        }
        return anss;
    }
    vector<int> tmp;
    for(auto i : H) tmp.push_back(i == 1 ? 1 : 0);
    Tree tr(n,tmp);
    //for(int i = 1;i < 2*tr.n;i++)cerr<<i<<" "<<tr.vals[i]<<" "<<tr.l_vals[i]<<" "<<tr.r_vals[i]<<endl;
    vector<ll> ans;
    for(int i = 0;i<q;i++){
        //cerr<<L[i]<<" "<<R[i]<<endl;
        //cerr<<"xd "<<tr.range_query(L[i],R[i]+1)<<endl;
        ans.push_back(2*(R[i] - L[i] + 1) - tr.range_query(L[i],R[i]+1));
    }
    return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'void setIO(std::string)':
meetings.cpp:11:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |   freopen((name+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
meetings.cpp:12:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   freopen((name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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