답안 #30134

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30134 2017-07-22T07:48:03 Z cdemirer 케이크 (CEOI14_cake) C++14
0 / 100
0 ms 12268 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:147:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("input", "r", stdin);
                              ^
cake.cpp:148:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("output", "w", stdout);
                                ^
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);
                         ^
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
2 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
3 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
4 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
5 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
6 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
7 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
8 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
2 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
3 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
4 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
5 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
6 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
7 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
2 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
3 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
4 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
5 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
6 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
7 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
8 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
9 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
10 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
11 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
12 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
13 Runtime error 0 ms 12268 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)