oj.uz

Submission #149553

# Submission time Handle Problem Language Result Execution time Memory
149553 2019-09-01T06:43:03 Z Seishun Buta Yarou wa Yumemiru Shoujo no Yume wo Minai(#3781, zscoder, tmwilliamlin168) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 3000 ms 98720 KB 
#include "squad.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

struct cht {
	int a[1<<18], b[1<<18], qt;
	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;
	}
	ll qry(ll x, ll y) {
		int lb=0, rb=qt-1;
		while(lb<rb) {
			int mb=(lb+rb)/2;
			if(a[mb]*x+b[mb]*y>a[mb+1]*x+b[mb+1]*y)
				rb=mb;
			else
				lb=mb+1;
		}
		return a[lb]*x+b[lb]*y;
	}
} ca[19][2], cd[19][2];

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)
			ca[j][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)
			cd[j][q[i]>>j&1].al(d[q[i]], p[q[i]]);
}

ll BestSquad(int x, int y) {
	ll ans=0;
	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));
	}
	return ans;
}

Compilation message

squad.cpp: In member function 'void cht::al(int, int)':
squad.cpp:11: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]))
         ~~^~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 848 ms 9464 KB Output is correct
4 Correct 780 ms 9476 KB Output is correct
5 Correct 42 ms 6392 KB Output is correct
6 Correct 742 ms 98680 KB Output is correct
7 Correct 724 ms 98680 KB Output is correct
8 Correct 731 ms 98720 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 15 ms 1048 KB Output is correct
3 Correct 1600 ms 11828 KB Output is correct
4 Correct 1525 ms 11720 KB Output is correct
5 Correct 111 ms 2920 KB Output is correct
6 Execution timed out 3103 ms 54136 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 848 ms 9464 KB Output is correct
4 Correct 780 ms 9476 KB Output is correct
5 Correct 42 ms 6392 KB Output is correct
6 Correct 742 ms 98680 KB Output is correct
7 Correct 724 ms 98680 KB Output is correct
8 Correct 731 ms 98720 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 15 ms 1048 KB Output is correct
11 Correct 1600 ms 11828 KB Output is correct
12 Correct 1525 ms 11720 KB Output is correct
13 Correct 111 ms 2920 KB Output is correct
14 Execution timed out 3103 ms 54136 KB Time limit exceeded
15 Halted 0 ms 0 KB -