제출 #79368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
79368		gs14004	모임들 (IOI18_meetings)	C++17	17 / 100	83 ms	8148 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using pi = pair<int, int>;
const int MAXN = 100005;
const int MAXT = 270005;
 
struct node{
	int len, le, ri, opt;
	node operator+(const node &n)const{
		node ret;
		ret.len = len + n.len;
		ret.le = (le == len ? (len + n.le) : le);
		ret.ri = (n.ri == n.len ? (ri + n.len) : n.ri);
		ret.opt = max({opt, n.opt, ri + n.le});
		return ret;
	}
};

struct seg{
	node tree[MAXT];
	int lim;
	void init(vector<int> &V){
		fill(tree, tree + MAXT, (node){0, 0, 0, 0});
		for(lim = 1; lim <= V.size(); lim <<= 1);
		for(int i=0; i<V.size(); i++){
			tree[i + lim].len = 1;
			if(V[i] == 1) tree[i + lim] = (node){1, 1, 1, 1};
		}
		for(int i=lim-1; i; i--) tree[i] = tree[2*i] + tree[2*i+1];
	}
	int query(int s, int e){
		s += lim;
		e += lim;
		node retl = {0, 0, 0, 0};
		node retr = {0, 0, 0, 0};
		while(s < e){
			if(s % 2 == 1) retl = retl + tree[s++];
			if(e % 2 == 0) retr = tree[e--] + retr;
			s >>= 1;
			e >>= 1;
		}
		if(s == e) retl = retl + tree[s];
		return (retl + retr).opt;
	}
}seg;

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
	int n = H.size();
	int q = L.size();
	seg.init(H);
	vector<long long> ret(q);
	for(int i=0; i<q; i++){
		ret[i] = 2 * (R[i] - L[i] + 1) - seg.query(L[i], R[i]);
	}
	return ret;
}

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

meetings.cpp: In member function 'void seg::init(std::vector<int>&)':
meetings.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(lim = 1; lim <= V.size(); lim <<= 1);
                ~~~~^~~~~~~~~~~
meetings.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<V.size(); i++){
                ~^~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:49:6: warning: unused variable 'n' [-Wunused-variable]
  int n = H.size();
      ^

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