oj.uz

Submission #30136

# Submission time Handle Problem Language Result Execution time Memory
30136 2017-07-22T07:49:01 Z cdemirer Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 24012 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef struct Node_ {
	int llim, rlim;
	int vmax;
} Node;
const int segsz = 524288;
const int offset = segsz / 2;
Node seg[segsz];
#define left(x) ((x)*2)
#define right(x) ((x)*2+1)
#define parent(x) ((x)/2)

int get(int x, int l, int r) {
	int llim = seg[x].llim;
	int rlim = seg[x].rlim;
	int mid = (llim + rlim) / 2;
	if (l == llim && r == rlim) return seg[x].vmax;
	else if (l > mid) return get(right(x), l, r);
	else if (r <= mid) return get(left(x), l, r);
	else {
		int a = get(left(x), l, mid);
		int b = get(right(x), mid+1, r);
		return max(a, b);
	}
}
void refresh(int x) {
	x = parent(x);
	while (x) {
		seg[x].vmax = max(seg[left(x)].vmax, seg[right(x)].vmax);
		x = parent(x);
	}
}
void change(int x, int p, int u) {
	int llim = seg[x].llim;
	int rlim = seg[x].rlim;
	int mid = (llim + rlim) / 2;
	if (llim == rlim) {
		seg[x].vmax = u;
		refresh(x);
	}
	else if (p > mid) change(right(x), p, u);
	else if (p <= mid) change(left(x), p, u);
	else {
		cerr << "Impossible branch" << endl;
	}
}

int N, A, Q;
set<ii> S;

int lbit[524289], rbit[524289];
int lbitget(int x) {
	int mxmm = 0;
	while (x > 0) {
		mxmm = max(mxmm, lbit[x]);
		x -= x & -x;
	}
	return mxmm;
}
int rbitget(int x) {
	int mxmm = 0;
	while (x > 0) {
		mxmm = max(mxmm, rbit[x]);
		x -= x & -x;
	}
	return mxmm;
}
void lbitmax(int x, int v) {
	while (x <= 524388) {
		lbit[x] = max(lbit[x], v);
		x += x & -x;
	}
}
void rbitmax(int x, int v) {
	while (x <= 524288) {
		rbit[x] = max(rbit[x], v);
		x += x & -x;
	}
}

int lbin(int w) {
	int l = 0, r = A;
	while (r > l) {
		int mid = (l+r)/2;
		if (lbitget(A-mid) > w) l = mid+1;
		else r = mid;
	}
	return l-1;
}
int rbin(int w) {
	int l = A, r = N-1;
	while (l < r) {
		int mid = (l+r+1)/2;
		if (rbitget(mid-A) > w) r = mid-1;
		else l = mid;
	}
	return r+1;
}

void addtt(int a, int b) {
	int oldv = seg[a+offset].vmax;
	S.erase(mp(oldv, a));
	set<ii>::iterator it = S.end();
	it--;
	for (int i = 0; i < b-1; i++) {
		ii q = *it;
		set<ii>::iterator it2 = it;
		it--;
		S.erase(it2);
		q.first += 1;
		S.insert(q);
		change(1, q.second, q.first);
		if (q.second < A) lbitmax(A-q.second, q.first);
		if (q.second > A) rbitmax(q.second-A, q.first);
	}
	ii qw;
	if (S.size() >= b) {
		qw = mp((*it).first+1, a);
	}
	else {
		exit(0);
		if (S.size() == 0) qw = mp(1, a);
		else {
			it = S.begin();
			qw = mp((*it).first+1, a);
		}
	}
	S.insert(qw);
	change(1, qw.second, qw.first);
	if (qw.second < A) lbitmax(A-qw.second, qw.first);
	if (qw.second > A) rbitmax(qw.second-A, qw.first);
}

int main(int argc, char **argv) {

	//freopen("input", "r", stdin);
	//freopen("output", "w", stdout);

	S.insert(mp(0, -1));
	scanf("%d%d", &N, &A);
	A--;
	vii arr;
	for (int i = offset; i < segsz; i++) {
		seg[i].llim = seg[i].rlim = i-offset;
		if (i-offset < N) {
			scanf("%d", &(seg[i].vmax));
			S.insert(mp(seg[i].vmax, i-offset));
		}
		else seg[i].vmax = 0;
	}
	for (int i = offset-1; i > 0; i--) {
		seg[i].llim = seg[left(i)].llim;
		seg[i].rlim = seg[right(i)].rlim;
		seg[i].vmax = max(seg[left(i)].vmax, seg[right(i)].vmax);
	}
	for (int i = A-1; i >= 0; i--) {
		lbitmax(A-i, seg[i+offset].vmax);
	}
	for (int i = A+1; i < N; i++) {
		rbitmax(i-A, seg[i+offset].vmax);
	}
	scanf("%d", &Q);
	char t;
	scanf("%c", &t);
	while (Q--) {
		scanf("%c", &t);
		if (t == 'E') {
			int a, b; scanf("%d%d", &a, &b);
			a--;
			addtt(a, b);
			/*for (int i = 0; i < N; i++) {
				cerr << seg[i+offset].vmax << " ";
			}
			cerr << endl;*/
		}
		else if (t == 'F') {
			int a; scanf("%d", &a);
			a--;
			if (a == A) {
				printf("0\n");
			}
			else if (a > A) {
				int m = get(1, A+1, a);
				int lp = lbin(m);
				printf("%d\n", a-lp-1);
			}
			else {
				int m = get(1, a, A-1);
				int rp = rbin(m);
				printf("%d\n", rp-a-1);
			}
		}
		else {
			cerr << "wrong type: " << t << endl;
			exit(-1);
		}
		if (Q) scanf("%c", &t);
	}

	return 0;
}

Compilation message

cake.cpp: In function 'void addtt(int, int)':
cake.cpp:128:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (S.size() >= b) {
               ^
cake.cpp: In function 'int main(int, char**)':
cake.cpp:151:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &A);
                       ^
cake.cpp:157:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &(seg[i].vmax));
                               ^
cake.cpp:173:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
cake.cpp:175:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%c", &t);
                 ^
cake.cpp:177:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &t);
                  ^
cake.cpp:179:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int a, b; scanf("%d%d", &a, &b);
                                   ^
cake.cpp:188:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int a; scanf("%d", &a);
                          ^
cake.cpp:208:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if (Q) scanf("%c", &t);
                         ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12264 KB Output is correct
2 Correct 0 ms 12264 KB Output is correct
3 Correct 3 ms 12264 KB Output is correct
4 Correct 6 ms 12264 KB Output is correct
5 Correct 36 ms 12792 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1079 ms 12660 KB Output is correct
2 Correct 549 ms 12792 KB Output is correct
3 Correct 753 ms 12792 KB Output is correct
4 Correct 453 ms 12792 KB Output is correct
5 Correct 1253 ms 13452 KB Output is correct
6 Correct 929 ms 13452 KB Output is correct
7 Correct 723 ms 13452 KB Output is correct
8 Correct 493 ms 13452 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 17016 KB Output is correct
2 Correct 143 ms 17016 KB Output is correct
3 Correct 143 ms 17016 KB Output is correct
4 Correct 0 ms 12264 KB Output is correct
5 Correct 486 ms 24012 KB Output is correct
6 Correct 436 ms 24012 KB Output is correct
7 Correct 193 ms 24012 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 12396 KB Output is correct
2 Correct 66 ms 12528 KB Output is correct
3 Correct 213 ms 14640 KB Output is correct
4 Correct 253 ms 14640 KB Output is correct
5 Correct 293 ms 12396 KB Output is correct
6 Correct 393 ms 15300 KB Output is correct
7 Correct 316 ms 12792 KB Output is correct
8 Correct 566 ms 17016 KB Output is correct
9 Execution timed out 2000 ms 24012 KB Execution timed out
10 Correct 913 ms 12396 KB Output is correct
11 Correct 1353 ms 13188 KB Output is correct
12 Execution timed out 2000 ms 21636 KB Execution timed out
13 Correct 1549 ms 24012 KB Output is correct