Submission #785108

#	Time	Username	Problem	Language	Result	Execution time	Memory
785108		QwertyPi	Meetings (IOI18_meetings)	C++14	17 / 100	83 ms	15024 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define INF (1 << 30)
#define INFL (1LL << 60)
#define fi first
#define se second
#define ll long long

using namespace std;
 
const int MAXN = 7.5e5 + 11;
const int LGN = 20;
long long fl[MAXN], fr[MAXN];

vector<int> h;

struct SparseTable{
	int t[LGN][MAXN];
	void init(vector<int> v){
		int N = v.size();
		for(int i = 0; i < N; i++) t[0][i] = v[i];
		for(int j = 1; j < LGN; j++) for(int i = 0; i <= N - (1 << j); i++) t[j][i] = max(t[j - 1][i], t[j - 1][i + (1 << j - 1)]);
	}
	long long qry(int l, int r){
		if(l > r) return 0;
		int d = __lg(r - l + 1);
		return max(t[d][l], t[d][r - (1 << d) + 1]);
	}
} st;

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    ::h = H;
    int N = H.size(), Q = L.size();
  	vector<int> cnt(N);
  	cnt[0] = H[0] == 1;
  	for(int i = 1; i < N; i++){
  		cnt[i] = H[i] == 1 ? cnt[i - 1] + 1 : 0;
	}
	st.init(cnt);
  	set<int> S;
  	for(int i = 0; i < N; i++){
  		if(H[i] == 2) S.insert(i);
	}
	vector<ll> C(Q); 
    for(int i = 0; i < Q; i++){
    	long long l = L[i], r = R[i];
    	int f = r + 1, t = l - 1;
		auto pf = S.lower_bound(l); if(pf != S.end()) f = *pf;
		auto sf = S.upper_bound(r); if(sf != S.begin()) t = *--sf;
		long long a2 = 0;
		a2 = max(f - l, r - t);
		a2 = max(a2, st.qry(f, t));
		C[i] = (r - l + 1) * 2 - min(r - l + 1, a2);
	}
  	return C;
}

Compilation message (stderr)

meetings.cpp: In member function 'void SparseTable::init(std::vector<int>)':
meetings.cpp:22:119: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   22 |   for(int j = 1; j < LGN; j++) for(int i = 0; i <= N - (1 << j); i++) t[j][i] = max(t[j - 1][i], t[j - 1][i + (1 << j - 1)]);
      |                                                                                                                     ~~^~~

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