oj.uz

답안 #150224

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
150224 2019-09-01T07:56:15 Z Seishun Buta Yarou wa Yumemiru Shoujo no Yume wo Minai(#3781, zscoder, tmwilliamlin168) 최적의 팀 구성 (FXCUP4_squad) C++17
19 / 100
 3000 ms 524288 KB 
#include "squad.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

bool cmp(int a0, int a1, int b0, int b1) {
	return (ll)a0*b1<(ll)b0*a1;
}

struct cht {
	int a[1<<18], b[1<<18], qt, ms;
	ar<int, 2> l[1<<18];
	ar<int, 4> m[1<<19];
	void al(int c, int d) {
		while(qt&&c==a[qt-1]||qt>1&&(ll)(b[qt-1]-b[qt-2])*(a[qt-1]-c)>=(ll)(d-b[qt-1])*(a[qt-2]-a[qt-1]))
			--qt;
		a[qt]=c;
		b[qt]=d;
		++qt;
	}
	void cl() {
		for(int i=0; i+1<qt; ++i)
			l[i]={b[i]-b[i+1], a[i+1]-a[i]};
		l[qt-1]={1<<30, 1};
	}
	void cm(vector<ar<int, 4>> &v) {
		for(int i=0, j=0; i<qt||j<v.size(); ++ms) {
			if(j>=v.size()||i<qt&&cmp(l[i][0], l[i][1], v[j][0], v[j][1])) {
				m[ms]={l[i][0], l[i][1], i, 2*j+1};
				++i;
			} else {
				m[ms]={v[j][0], v[j][1], i, 2*j+1};
				++j;
			}
		}
		//for(ar<int, 4> mi : m)
			//cout << "{" << mi[0] << " " << mi[1] << " " << mi[2] << " " << mi[3] << "} ";
		//cout << endl;
	}
} c[76];

int n, k, q[300000];

void Init(vector<int> a, vector<int> d, vector<int> p) {
	n=a.size();
	while(1<<k<n)
		++k;
	iota(q, q+n, 0);
	sort(q, q+n, [&](const int &i, const int &j) {
		return ar<int, 2>{a[i], p[i]}<ar<int, 2>{a[j], p[j]};
	});
	for(int i=0; i<n; ++i)
		for(int j=0; j<k; ++j)
			c[j*4+(q[i]>>j&1)].al(a[q[i]], p[q[i]]);
	sort(q, q+n, [&](const int &i, const int &j) {
		return ar<int, 2>{d[i], p[i]}<ar<int, 2>{d[j], p[j]};
	});
	for(int i=0; i<n; ++i)
		for(int j=0; j<k; ++j)
			c[j*4+2+(q[i]>>j&1)].al(d[q[i]], p[q[i]]);
	//cout << "hi0" << endl;
	for(int i=0; i<k*4; ++i) {
		c[i].cl();
	}
	//cout << "hi1" << endl;
	for(int i=k*4-1; ~i; --i) {
		vector<ar<int, 4>> v;
		if(i+1<k*4)
			for(int j=1; j<c[i+1].ms; j+=2)
				v.push_back(c[i+1].m[j]);
		c[i].cm(v);
	}
	//cout << "hi2" << endl;
}

ll BestSquad(int x, int y) {
	//cout << "bs " << x << " " << y << endl;
	ll ans=0, d[k*4];
	//for(int i=0; i<k*4; ++i)
		//d[i]=c[i].qry(x, y);
	//frucktional cascading
	int lb=1, rb=c[0].ms-1;
	while(lb<rb) {
		int mb=(lb+rb)/2;
		if(!cmp(c[0].m[mb][0], c[0].m[mb][1], x, y))
			rb=mb;
		else
			lb=mb+1;
	}
	//cout << "hi3 " << lb << endl;
	for(int i=0; i<k*4; ++i) {
		if(!cmp(c[i].m[lb-1][0], c[i].m[lb-1][1], x, y))
			--lb;
		//cout << i << " " << lb << endl;
		int j=c[i].m[lb][2];
		//cout << j << endl;
		lb=c[i].m[lb][3];
		d[i]=(ll)x*c[i].a[j]+(ll)y*c[i].b[j];
	}
	for(int i=0; i<k; ++i) {
		//ans=max(ans, ca[i][0].qry(x, y)+cd[i][1].qry(x, y));
		//ans=max(ans, cd[i][0].qry(x, y)+ca[i][1].qry(x, y));
		ans=max(ans, d[i*4]+d[i*4+3]);
		ans=max(ans, d[i*4+1]+d[i*4+2]);
	}
	return ans;
}

Compilation message

squad.cpp: In member function 'void cht::al(int, int)':
squad.cpp:17:11: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   while(qt&&c==a[qt-1]||qt>1&&(ll)(b[qt-1]-b[qt-2])*(a[qt-1]-c)>=(ll)(d-b[qt-1])*(a[qt-2]-a[qt-1]))
         ~~^~~~~~~~~~~~
squad.cpp: In member function 'void cht::cm(std::vector<std::array<int, 4> >&)':
squad.cpp:29:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0, j=0; i<qt||j<v.size(); ++ms) {
                           ~^~~~~~~~~
squad.cpp:30:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(j>=v.size()||i<qt&&cmp(l[i][0], l[i][1], v[j][0], v[j][1])) {
       ~^~~~~~~~~~
squad.cpp:30:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if(j>=v.size()||i<qt&&cmp(l[i][0], l[i][1], v[j][0], v[j][1])) {
                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 8 ms 1536 KB Output is correct
3 Correct 852 ms 10872 KB Output is correct
4 Correct 857 ms 10872 KB Output is correct
5 Correct 71 ms 30848 KB Output is correct
6 Correct 1384 ms 524288 KB Output is correct
7 Correct 1359 ms 524288 KB Output is correct
8 Correct 1356 ms 524288 KB Output is correct

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 19 ms 1792 KB Output is correct
3 Correct 2212 ms 13108 KB Output is correct
4 Correct 2203 ms 12980 KB Output is correct
5 Correct 112 ms 10560 KB Output is correct
6 Execution timed out 3114 ms 278684 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 8 ms 1536 KB Output is correct
3 Correct 852 ms 10872 KB Output is correct
4 Correct 857 ms 10872 KB Output is correct
5 Correct 71 ms 30848 KB Output is correct
6 Correct 1384 ms 524288 KB Output is correct
7 Correct 1359 ms 524288 KB Output is correct
8 Correct 1356 ms 524288 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 19 ms 1792 KB Output is correct
11 Correct 2212 ms 13108 KB Output is correct
12 Correct 2203 ms 12980 KB Output is correct
13 Correct 112 ms 10560 KB Output is correct
14 Execution timed out 3114 ms 278684 KB Time limit exceeded
15 Halted 0 ms 0 KB -