Submission #1045331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045331		wood	Meetings (IOI18_meetings)	C++17	17 / 100	112 ms	123340 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int N = 1e7;

struct segtree{
    using t = tuple<int,int,int>;
    int size = 1; t arr[N] = {t(0,0,0)};
    segtree(int n){while(size<n) size*=2;}

	void merge(t l, t r, t& result, int lx, int rx, int m) {

		if(get<1>(l)==m-lx){
			if(get<1>(r)==m-lx) result = t(rx-lx,rx-lx,rx-lx);
			else result = t((get<1>(r))+m-lx,(get<1>(r))+m-lx, get<2>(r));
		}
		else if(get<1>(r)==m-lx) result = t((get<2>(l))+m-lx,get<1>(l), (get<2>(l))+m-lx);
		else
			result = t(max(max(get<0>(l),get<0>(r)), (get<1>(r))+get<2>(l))
			,get<1>(l), get<2>(r));
    }
    void set(int i, int u){
	set(i,u,0,0,size);
    }
    void set(int i, int u, int x, int lx, int rx){
		if(rx-lx==1){
		    if(u==2) arr[x] = t(0,0,0);
		    else arr[x] = t(1,1,1);
		    return;
		}
		int m = (rx+lx)/2;
		if(i<m) set(i,u,2*x+1,lx,m);
		else set(i,u,2*x+2,m,rx);
		merge(arr[2*x+1],arr[2*x+2],arr[x],lx,rx,m);
    }
    t goat(int l, int r){
	    return goat(l,r,0,0,size);
    }
    t goat(int l, int r, int x, int lx, int rx){
	    if(rx<=l||lx>=r) return t(0,0,0);
	    if(rx<=r&&lx>=l) return arr[x];
	    int m = (rx+lx)/2;
	    t res;
	    merge(goat(l,r,2*x+1,lx,m), goat(l,r,2*x+2,m,rx), res,lx,rx,m);
	    return res;
    }
};

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    int Q = L.size();
    vector<long long> C;
    int n = H.size();
    segtree sgt(n);
    for(int i = 0; i<n; i++)
    	sgt.set(i,H[i]);
    for(int i = 0; i<Q; i++){
    	//cout<<get<0>(sgt.goat(L[i],R[i]+1))<<'\n';
	    C.push_back(2*(R[i]-L[i]+1)-get<0>(sgt.goat(L[i], R[i]+1)));
    }
    return C;
}

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