oj.uz

답안 #150121

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
150121 2019-09-01T07:45:39 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(ar<int, 2> a, ar<int, 2> b) {
	return (ll)a[0]*b[1]<(ll)b[0]*a[1];
}

struct cht {
	int a[1<<18], b[1<<18], qt;
	ar<int, 2> l[1<<18];
	vector<ar<int, 4>> m;
	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(); ) {
			if(j>=v.size()||i<qt&&cmp(l[i], {v[j][0], v[j][1]})) {
				m.push_back({l[i][0], l[i][1], i, 2*j+1});
				++i;
			} else {
				m.push_back({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].m.size(); 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].m.size()-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(); ) {
                           ~^~~~~~~~~
squad.cpp:30:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(j>=v.size()||i<qt&&cmp(l[i], {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], {v[j][0], v[j][1]})) {
                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=1; j<c[i+1].m.size(); j+=2)
                 ~^~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 786 ms 10128 KB Output is correct
4 Correct 758 ms 10104 KB Output is correct
5 Correct 68 ms 30612 KB Output is correct
6 Correct 1275 ms 524288 KB Output is correct
7 Correct 1309 ms 524288 KB Output is correct
8 Correct 1308 ms 524288 KB Output is correct

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1152 KB Output is correct
2 Correct 13 ms 1664 KB Output is correct
3 Correct 1364 ms 12468 KB Output is correct
4 Correct 1343 ms 12464 KB Output is correct
5 Correct 118 ms 11700 KB Output is correct
6 Execution timed out 3115 ms 302420 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 786 ms 10128 KB Output is correct
4 Correct 758 ms 10104 KB Output is correct
5 Correct 68 ms 30612 KB Output is correct
6 Correct 1275 ms 524288 KB Output is correct
7 Correct 1309 ms 524288 KB Output is correct
8 Correct 1308 ms 524288 KB Output is correct
9 Correct 6 ms 1152 KB Output is correct
10 Correct 13 ms 1664 KB Output is correct
11 Correct 1364 ms 12468 KB Output is correct
12 Correct 1343 ms 12464 KB Output is correct
13 Correct 118 ms 11700 KB Output is correct
14 Execution timed out 3115 ms 302420 KB Time limit exceeded
15 Halted 0 ms 0 KB -