Submission #59071

#	Time	Username	Problem	Language	Result	Execution time	Memory
59071		Just_Solve_The_Problem	Holiday (IOI14_holiday)	C++11	Compilation error	0 ms	0 KiB

holiday

#include"grader.cpp"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()

const int N = (int)1e5 + 7;

struct T {
	ll sum;
	int cnt;
	T() {
		sum = cnt = 0;
	}
};

struct TT {
	T tree[N * 4];
	void upd(int pos, int val, int v = 1, int l = 1, int r = N) {
		if (l == r) {
			if (val == -1) {
				tree[v].sum = 0;
				tree[v].cnt = 0;
			} else {
				tree[v].sum = val;
				tree[v].cnt = 1;
			}
			return ;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) {
			upd(pos, val, v + v, l, mid);
		} else {
			upd(pos, val, v + v + 1, mid + 1, r);
		}
		tree[v].sum = tree[v + v].sum + tree[v + v + 1].sum;
		tree[v].cnt = tree[v + v].cnt + tree[v + v + 1].cnt;
	}
	ll get(int take, int v = 1, int l = 1, int r = N) {
		if (l == r) {
			return ((take > 0) ? tree[v].sum : 0);
		}
		int mid = (l + r) >> 1;
		if (tree[v + v + 1].cnt >= take) {
			return get(take, v + v + 1, mid + 1, r);
		} else {
			return get(take - tree[v + v + 1].cnt, v + v, l, mid) + tree[v + v + 1].sum;
		}
	}
};
TT tr;

vector < int > a, b, A, B, a1, b1;
ll c[5][N * 3];

bool cmpa(int x, int y) {
	return A[x] < A[y];
}

bool cmpb(int x, int y) {
	return B[x] < B[y];
}

void divide(int id, int l, int r, int optl, int optr) {
	if (l > r) return ;
	int opt = optl;
	ll best = -1;
	int mid = (l + r) >> 1;
	for (int i = optl; i <= optr; i++) {
		if (id <= 2) {
			tr.upd(a1[i], A[i]);
		} else {
			tr.upd(b1[i], B[i]);
		}
		ll cost = tr.get(mid - (i + 1) - ((id & 1 ^ 1) ? (i + 1) : 0));
		if (cost > best) {
			best = cost;
			opt = i;
		}
	}
	for (int i = optl; i <= optr; i++) {
		tr.upd(a1[i], -1);
		tr.upd(b1[i], -1);
	}
	divide(id, l, mid - 1, optl, opt);
	divide(id, mid + 1, r, opt, optr);
	c[id][mid] = best;
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	for (int i = 0; i < n; i++) {
		if (i < start) {
			A.pb(attraction[i]);
			a.pb(i);
		} else if (i > start) {
			B.pb(attraction[i]);
			b.pb(i - start - 1);
		}
	}
	reverse(all(A));
	sort(all(a), cmpa);
	sort(all(b), cmpb);
	a1.resize(n);
	b1.resize(n);
	for (int i = 0; i < sz(a); i++) 
		a1[a[i]] = i;
	for (int i = 0; i < sz(b); i++) 
		b1[b[i]] = i;
	if (!a.empty()) {
		divide(1, 1, d, 0, sz(a) - 1);
		divide(2, 1, d, 0, sz(a) - 1);
	}
	if (!b.empty()) {
		divide(3, 1, d, 0, sz(b) - 1);
		divide(4, 1, d, 0, sz(b) - 1);
	}
	ll ans = 0;
	
	for (int i = 1; i < d; i++) {
		ans = max(ans, c[1][i] + attraction[start] + c[4][d - i - 1]);
		ans = max(ans, c[3][i] + attraction[start] + c[2][d - i - 1]);
		ans = max(ans, c[1][i] + c[4][d - i]);
		ans = max(ans, c[3][i] + c[2][d - i]);
	}
	ans = max(ans, c[1][d] + c[4][0]);
	ans = max(ans, c[3][d] + c[2][0]);
	return ans;
}

Compilation message (stderr)

In file included from holiday.cpp:1:0:
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~
holiday.cpp: In function 'void divide(int, int, int, int, int)':
holiday.cpp:79:41: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   ll cost = tr.get(mid - (i + 1) - ((id & 1 ^ 1) ? (i + 1) : 0));
                                      ~~~^~~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~
/tmp/ccfZ0yv1.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc9D6Xtn.o:holiday.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status