oj.uz

Submission #149669

# Submission time Handle Problem Language Result Execution time Memory
149669 2019-09-01T06:56:06 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 99324 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;
	ar<int, 2> l[1<<18];
	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;
	}
	void cl() {
		for(int i=0; i<qt; ++i) {
			;
		}
	}
} 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]]);
	for(int i=0; i<k*4; ++i) {
		c[i].cl();
	}
}

ll BestSquad(int x, int y) {
	ll ans=0, d[k*4];
	for(int i=0; i<k*4; ++i)
		d[i]=c[i].qry(x, y);
	//frucktional cascading
	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:12: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 6 ms 512 KB Output is correct
2 Correct 7 ms 1152 KB Output is correct
3 Correct 792 ms 10100 KB Output is correct
4 Correct 830 ms 10104 KB Output is correct
5 Correct 40 ms 6904 KB Output is correct
6 Correct 647 ms 99320 KB Output is correct
7 Correct 638 ms 99324 KB Output is correct
8 Correct 639 ms 99320 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 16 ms 1408 KB Output is correct
3 Correct 1995 ms 12344 KB Output is correct
4 Correct 1999 ms 12340 KB Output is correct
5 Correct 115 ms 3304 KB Output is correct
6 Execution timed out 3103 ms 54648 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 7 ms 1152 KB Output is correct
3 Correct 792 ms 10100 KB Output is correct
4 Correct 830 ms 10104 KB Output is correct
5 Correct 40 ms 6904 KB Output is correct
6 Correct 647 ms 99320 KB Output is correct
7 Correct 638 ms 99324 KB Output is correct
8 Correct 639 ms 99320 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 16 ms 1408 KB Output is correct
11 Correct 1995 ms 12344 KB Output is correct
12 Correct 1999 ms 12340 KB Output is correct
13 Correct 115 ms 3304 KB Output is correct
14 Execution timed out 3103 ms 54648 KB Time limit exceeded
15 Halted 0 ms 0 KB -