Submission #1304562
Source Code Expand
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <nmmintrin.h>
#include <chrono>
#include <list>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b) ((a >> b) & 1)
#define bitset(a,b) ( a |= (1 << b))
#define bitunset(a,b) (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589
#ifdef _MSC_VER
#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
std::fill((T*)array, (T*)(array + N), val);
}
class Bitvector {
//4byteブロック 全部半径、0-index
const int bsize = 8;
static const int popc[256];
public:
unsigned char* st;
unsigned int* blockrank;
int sz;
Bitvector(int n) {
sz = n;
st = (unsigned char*)calloc((n + bsize - 1) / bsize, sizeof(char));
blockrank = (unsigned int*)calloc((n + bsize - 1) / bsize + 1, sizeof(int));
if (st == NULL || blockrank == NULL)
abort();
}
inline void set(int a, bool f) {//後から追加はできない
if (f)bitset(st[a / bsize], (bsize - 1 - a % bsize));
}
inline bool get(int a) { return bitcheck(st[a / bsize], (bsize - 1 - a % bsize)); }
inline void calcblock() {
int cou = 0;
REP(i, sz + 1) {
if (i && !(i % 8))blockrank[i / bsize] = cou;
if (i<sz)cou += bitcheck(st[i / bsize], (bsize - 1 - i % bsize));
}
}
int rank(int a, bool t) {
int ret = blockrank[a / bsize] + (((bsize - a % bsize) >= bsize) ? 0 : popc[st[a / bsize] >> (bsize - a % bsize)]);
return t ? ret : a - ret;
}
int select(int a, bool t) {
int l = 0, r = sz + 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (rank(mid, t) >= a) r = mid;
else l = mid;
}
if (rank(r, t) < a) return -1;
return r;
}
void clear() {
free(st);
free(blockrank);
}
};
const int Bitvector::popc[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };
//プリミティブ型だけだよ!!!!(低レベルでうぇぶるので) 数値比較系使うときはunsignedのみ!!!!!
template<typename T>
class WaveletMatrix {
#define tbitcheck(a,b) (((T)a >> b) & 1)
#define tbitset(a,b) ( a |= ((T)1 << b))
#define tbitunset(a,b) (a &= ~((T)1 << b))
public:
vector<T> data;
vector<ll> rui;
vector<vector<ll>> bitrui;
vector<Bitvector> bitv;
vector<int> border;
int bitsize;
WaveletMatrix(vector<T>& dat) : bitsize(sizeof(T) * 8), data(dat), border(sizeof(T) * 8 +1), rui(data.size()+1), bitrui(sizeof(T)*8) {
bitv.reserve(bitsize);
REP(i, bitsize + 1)
bitv.push_back(Bitvector(data.size()));
REP(j, data.size()) {
bitv[0].set(j, tbitcheck(data[j], bitsize - 1));
rui[j+1] = rui[j] + data[j];
}
bitv[0].calcblock();
vector<T> buf[2];
buf[0] = data;
buf[1].resize(data.size());
REP(i, bitsize - 1) {
border[i + 1] = bitv[i].rank(data.size(), 0);
int cou[2] = { 0, border[i + 1] };
bitrui[i].resize(data.size()+1);
REP(j, data.size()) {
if(tbitcheck(buf[i % 2][j], bitsize - i - 1))
bitrui[i][j + 1] = buf[i % 2][j];
bitrui[i][j + 1] += bitrui[i][j];
bitv[i + 1].set(cou[bitv[i].get(j)], tbitcheck(buf[i % 2][j], bitsize - i - 2));
buf[1 - i % 2][cou[bitv[i].get(j)]] = tbitunset(buf[i % 2][j], (bitsize - i - 1));
cou[bitv[i].get(j)]++;
}
bitv[i + 1].calcblock();
}
bitrui[bitsize-1].resize(data.size()+1);
REP(j, data.size()) {
if (tbitcheck(buf[(bitsize - 1) % 2][j], 0))
bitrui[bitsize - 1][j + 1] = buf[(bitsize - 1) % 2][j];
bitrui[bitsize-1][j+1] += bitrui[bitsize - 1][j];
}
border[bitsize] = bitv[bitsize - 1].rank(data.size(), 0);
}
pii search(int s, int e, unsigned int t, int b = 0) {
if (b == bitsize) return{ s,e };
bool cur = tbitcheck(t, bitsize - 1);
return search(cur*border[b + 1] + bitv[b].rank(s, cur), cur*border[b + 1] + bitv[b].rank(e, cur), t << 1, b + 1);
}
int backward(int a, unsigned int t, int b = 0) {
if (b == bitsize - 1) return a;
backward(bitv[bitsize - b - 1].select(a + 1 - tbitcheck(t, 0) * border[bitsize - b], tbitcheck(t, 0)) - 1, t >> 1, b + 1);
}
int rank(int s, int e, T t) {
pii r = search(s, e, t);
return r.second - r.first;
}
int select(int a, T t) {
pii r = search(0, data.size(), t);
return backward(r.first + a - 1, t);
}
T less_kthelement(int s, int e, int k, int b = 0) {//小さいほうから 0番目~
int eo = bitv[b].rank(e, 0), so = bitv[b].rank(s, 0), cou = eo - so;
if (b == bitsize - 1) return cou <= k;
return (cou <= k ?
less_kthelement(border[b + 1] + (s - so), border[b + 1] + (s - so) + (e - s - cou), k - cou, b + 1) :
less_kthelement(so, so + cou, k, b + 1)) | ((cou <= k) << (bitsize - b - 1));
}
T more_kthelement(int s, int e, int k, int b = 0) {//上からk個のsum 0番目~
int eo = bitv[b].rank(e, 1), so = bitv[b].rank(s, 1), cou = eo - so;
if (b == bitsize - 1) return cou > k;
return (cou > k ?
more_kthelement(border[b + 1]+so, border[b + 1]+ so + cou, k, b + 1) :
more_kthelement(s-so, (s - so) + (e - s - cou), k - cou, b + 1)) | ((cou > k) << (bitsize - b - 1));
}
ll more_kthsum(int s, int e, int k, int b = 0) {//大きいほうからk個
if (k <= 0) return 0;
int eo = bitv[b].rank(e, 1), so = bitv[b].rank(s, 1), cou = eo - so;
if (b == bitsize - 1) return min(k,cou);
if (cou >= k) {
ll ret = more_kthsum(border[b + 1] + so, border[b + 1] + so + cou, k, b + 1);
return ret + (ll)min(k, cou) * (1 << (bitsize - b - 1));
}
else {
ll ret = more_kthsum(s - so, (s - so) + (e - s - cou), k - cou, b + 1);
return ret + (bitrui[b][e] - bitrui[b][s]) + (ll)min(k, max(0,cou - k)) * (1 << (bitsize - b - 1));
}
}
ll less_kthsum(int s, int e, int k, int b = 0) {//小さいほうからk個
return (rui[e] - rui[s]) - more_kthsum(s, e, (e - s) - k);
}
int less(int s, int e, T t, int b = 0) {
int eo = bitv[b].rank(e, 0), so = bitv[b].rank(s, 0), cou = (eo - so);
if (b == bitsize) return e - s;
return tbitcheck(t, bitsize - b - 1) ?
less(border[b + 1] + (s - so), border[b + 1] + (s - so) + (e - s - cou), t, b + 1) + cou :
less(so, so + cou, t, b + 1);
}
~WaveletMatrix() {
REP(i, bitsize) bitv[i].clear();
}
};
signed main() {
int n;
scanf("%d", &n);
vector<int> num(n*3);
REP(i, n*3) {
scnaf("%d", &num[i]);
}
vector<int> buf(n*3);
copy(ALL(num), buf.begin());
WaveletMatrix<int> wv(num);
ll Max = LLONG_MIN;
rep(i, n, n*2+1) {
ll b = wv.more_kthsum(0, i, n), c = wv.less_kthsum(i, n * 3, n);
Max = max(Max, b - c);
}
printf("%lld\n", Max);
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 3N Numbers |
User |
Gear |
Language |
C++14 (Clang 3.8.0) |
Score |
500 |
Code Size |
8388 Byte |
Status |
AC |
Exec Time |
597 ms |
Memory |
89472 KB |
Judge Result
Set Name |
Sample |
Subtask |
All |
Score / Max Score |
0 / 0 |
300 / 300 |
200 / 200 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
Subtask |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
8 ms |
1016 KB |
0_01.txt |
AC |
1 ms |
256 KB |
0_02.txt |
AC |
1 ms |
256 KB |
1_00.txt |
AC |
2 ms |
384 KB |
1_01.txt |
AC |
1 ms |
256 KB |
1_02.txt |
AC |
1 ms |
256 KB |
1_03.txt |
AC |
1 ms |
256 KB |
1_04.txt |
AC |
1 ms |
256 KB |
1_05.txt |
AC |
1 ms |
256 KB |
1_06.txt |
AC |
1 ms |
256 KB |
1_07.txt |
AC |
1 ms |
256 KB |
1_08.txt |
AC |
5 ms |
1152 KB |
1_09.txt |
AC |
5 ms |
1152 KB |
1_10.txt |
AC |
5 ms |
1152 KB |
1_11.txt |
AC |
5 ms |
1152 KB |
1_12.txt |
AC |
5 ms |
1152 KB |
1_13.txt |
AC |
5 ms |
1152 KB |
1_14.txt |
AC |
5 ms |
1152 KB |
1_15.txt |
AC |
5 ms |
1152 KB |
1_16.txt |
AC |
5 ms |
1152 KB |
1_17.txt |
AC |
5 ms |
1152 KB |
1_18.txt |
AC |
5 ms |
1152 KB |
1_19.txt |
AC |
5 ms |
1152 KB |
1_20.txt |
AC |
7 ms |
1152 KB |
1_21.txt |
AC |
7 ms |
1152 KB |
1_22.txt |
AC |
7 ms |
1152 KB |
1_23.txt |
AC |
7 ms |
1152 KB |
2_00.txt |
AC |
452 ms |
89344 KB |
2_01.txt |
AC |
465 ms |
89344 KB |
2_02.txt |
AC |
437 ms |
89344 KB |
2_03.txt |
AC |
460 ms |
89344 KB |
2_04.txt |
AC |
414 ms |
89344 KB |
2_05.txt |
AC |
421 ms |
89344 KB |
2_06.txt |
AC |
413 ms |
89344 KB |
2_07.txt |
AC |
427 ms |
89344 KB |
2_08.txt |
AC |
435 ms |
88192 KB |
2_09.txt |
AC |
562 ms |
87936 KB |
2_10.txt |
AC |
446 ms |
88704 KB |
2_11.txt |
AC |
432 ms |
87680 KB |
2_12.txt |
AC |
591 ms |
88448 KB |
2_13.txt |
AC |
594 ms |
89472 KB |
2_14.txt |
AC |
592 ms |
89344 KB |
2_15.txt |
AC |
597 ms |
89088 KB |