oj.uz

답안 #30135

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30135 2017-07-22T07:48:28 Z cdemirer 케이크 (CEOI14_cake) C++14
20 / 100
 2000 ms 24016 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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 12268 KB Output is correct
2 Correct 19 ms 12268 KB Output is correct
3 Correct 66 ms 12268 KB Output is correct
4 Runtime error 69 ms 12268 KB Execution timed out (wall clock limit exceeded)
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 56 ms 12664 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 146 ms 12796 KB Execution timed out (wall clock limit exceeded)
3 Execution timed out 2000 ms 12796 KB Execution timed out
4 Execution timed out 2000 ms 12796 KB Execution timed out
5 Execution timed out 2000 ms 13456 KB Execution timed out
6 Execution timed out 2000 ms 13456 KB Execution timed out
7 Execution timed out 2000 ms 13456 KB Execution timed out
8 Execution timed out 2000 ms 13456 KB Execution timed out

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 746 ms 17020 KB Output is correct
2 Correct 619 ms 17020 KB Output is correct
3 Correct 646 ms 17020 KB Output is correct
4 Correct 0 ms 12268 KB Output is correct
5 Correct 1366 ms 24016 KB Output is correct
6 Correct 1446 ms 24016 KB Output is correct
7 Correct 1353 ms 24016 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2000 ms 12400 KB Execution timed out
2 Execution timed out 2000 ms 12532 KB Execution timed out
3 Execution timed out 2000 ms 14644 KB Execution timed out
4 Execution timed out 2000 ms 14644 KB Execution timed out
5 Execution timed out 2000 ms 12400 KB Execution timed out
6 Execution timed out 2000 ms 15304 KB Execution timed out
7 Execution timed out 2000 ms 12796 KB Execution timed out
8 Execution timed out 2000 ms 17020 KB Execution timed out
9 Execution timed out 2000 ms 24016 KB Execution timed out
10 Execution timed out 2000 ms 12400 KB Execution timed out
11 Execution timed out 2000 ms 13192 KB Execution timed out
12 Execution timed out 2000 ms 21640 KB Execution timed out
13 Execution timed out 2000 ms 24016 KB Execution timed out