제출 #75194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75194		Adhyyan1252	모임들 (IOI18_meetings)	C++11	0 / 100	5509 ms	40468 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
struct segment{
	vector<ll> t;
	int n;
	
	segment (int size = 0){
		n = size;
		t.resize(n*2);
	}
	
	segment(vector<ll>& a){
		n = t.size();
		t.resize(n*2);
		for(int i = n; i < 2*n; i++){
			t[i] = a[i-n];
		}
 		for(int i = n-1; i > 0; i--){
			t[i] = max(t[i*2], t[i*2+1]);
		}
	}
	
	void build(){
		for(int i = 0; i < n; i++){
			t[i+n] = t[i];
		}
		for(int i = n-1; i > 0; i--){
			t[i] = max(t[i*2], t[i*2+1]);
		}
	}
	
	ll query(int l, int r){
		ll ans = 0;
		for(l += n, r += n+1; r > l; l>>=1, r>>=1){
			if(l&1) ans = max(ans, t[l++]);
			if(r&1) ans = max(ans, t[--r]);
		}
		return ans;
	}
	
};
#define HMAX 22
segment s[HMAX+1];

vector<int> h;
vector<vector<int> > g;

void preprocess(){
	g.resize(HMAX+1);
	for(int i = 0; i < h.size(); i++)
		g[h[i]].push_back(i);
	for(int i = 0; i <= HMAX; i++){
		s[i] = segment(h.size());
	}
}

ll pre(int l, int r, int val){
	//cout<<"P "<<l<<" "<<r<<" "<<val<<endl;
	if(l > r) return 0;
	if(val == 1){
		for(int i = l; i <= r; i++){
			s[val].t[i] = r - l + 1;
		}
		return r - l + 1;
	}
	if(l == r) return (val - h[l] + 1);
	vector<int>& c = g[val];
	ll ans = 0;
	if(c.size() == 0) ans = pre(l, r, val-1);
	else{
		int lp = lower_bound(c.begin(), c.end(), l) - c.begin();
		int rp = upper_bound(c.begin(), c.end(), r) - c.begin() - 1;
		if(lp == c.size() || c[lp] > r){
			ans = pre(l, r, val-1);
		}else{
			ans = max(ans, pre(l, c[lp]-1, val-1));
			ans = max(ans, pre(c[rp]+1, r, val-1));
			for(int i = lp; i < rp; i++){
				if(c[i] + 1 < c[i+1]) ans = max(ans, pre(c[i]+1, c[i+1]-1, val-1));
			}
		}
	}
	ans += r - l + 1;
	for(int i = l; i <= r; i++){
		s[val].t[i] = ans;
	}
	return ans;
}

ll query(int l, int r, int val, bool lc, bool rc){
	if(l > r) return 0;
	if(l == r) return (val - h[l] + 1);
	if(val == 1) return (r - l + 1);
	vector<int>& c = g[val];
	ll ans = 0;
	int lp = lower_bound(c.begin(), c.end(), l) - c.begin();
	int rp = upper_bound(c.begin(), c.end(), r) - c.begin() - 1;
	if(lp == c.size() || c[lp] > r){
		ans = pre(l, r, val-1);
	}else{	
		if(!lc && !rc){
			ans = s[val-1].query(c[lp], c[rp]);
			ans = max(ans, query(l, c[lp]-1, val-1, false, true));
			ans = max(ans, query(c[rp]+1, r, val-1, true, false));
		}else if(!lc && rc){
			ans = s[val-1].query(c[lp], r);
			ans = max(ans, query(l, c[lp]-1, val-1, false, true));
		}else if(!rc && lc){
			ans = s[val-1].query(l, c[rp]);
			ans = max(ans, query(c[rp]+1, r, val-1, true, false));
		}//else abort();
	}
	ans += r - l + 1;
	return ans;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    //cout<<"WALLA "<<endl;
	int Q = L.size();
	h = H;
	for(int i = 0; i < H.size(); i++){
		if(h[i] > HMAX) return vector<long long>(L.size());
	}
	std::vector<long long> C(Q);
	//cout<<"STARTING"<<endl;
	preprocess();
	pre(0, h.size()-1, HMAX);
	//abort();
	//cout<<"PRE DONE"<<endl;
	for(int i = 0; i <= HMAX; i++){
		s[i].build();
	}
	for(int i = 0; i < Q; i++){
		C[i] = (R[i] - L[i] + 1LL)*(HMAX + 1) - query(L[i], R[i], HMAX, false, false);
	}
  	return C;
}

컴파일 시 표준 에러 (stderr) 메시지

meetings.cpp: In function 'void preprocess()':
meetings.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < h.size(); i++)
                 ~~^~~~~~~~~~
meetings.cpp: In function 'll pre(int, int, int)':
meetings.cpp:76:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(lp == c.size() || c[lp] > r){
      ~~~^~~~~~~~~~~
meetings.cpp: In function 'll query(int, int, int, bool, bool)':
meetings.cpp:101:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(lp == c.size() || c[lp] > r){
     ~~~^~~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:125:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < H.size(); i++){
                 ~~^~~~~~~~~~

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