답안 #30146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30146 2017-07-22T08:11:22 Z cdemirer 케이크 (CEOI14_cake) C++14
100 / 100
1063 ms 15420 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;
vii topten;

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);*/
	for (int i = 0; i < topten.size(); i++) {
		if (topten[i].second == a) {
			//cerr << a << endl;
			topten.erase(topten.begin()+i);
			break;
		}
	}
	for (int i = 0; i < b-1; i++) {
		topten[i].first++;
		change(1, topten[i].second, topten[i].first);
		if (topten[i].second < A) lbitmax(A-topten[i].second, topten[i].first);
		if (topten[i].second > A) rbitmax(topten[i].second-A, topten[i].first);
	}
	if (b!=1) topten.insert(topten.begin()+b-1, mp(topten[b-2].first-1, a));
	else topten.insert(topten.begin(), mp(topten[0].first+1, a));
	//else exit(-1);
	change(1, topten[b-1].second, topten[b-1].first);
	if (topten[b-1].second < A) lbitmax(A-topten[b-1].second, topten[b-1].first);
	if (topten[b-1].second > A) rbitmax(topten[b-1].second-A, topten[b-1].first);
	topten.resize(min((int)topten.size(), 10));
}

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));
			topten.pb(mp(seg[i].vmax, i-offset));
		}
		else seg[i].vmax = 0;
	}
	sort(topten.begin(), topten.end());
	reverse(topten.begin(), topten.end());
	topten.resize(min((int)topten.size(), 10));
	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:144:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < topten.size(); i++) {
                    ^
cake.cpp: In function 'int main(int, char**)':
cake.cpp:172: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:178: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:198:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
cake.cpp:200:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%c", &t);
                 ^
cake.cpp:202:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &t);
                  ^
cake.cpp:204: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:213: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:233: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 Correct 0 ms 12264 KB Output is correct
2 Correct 0 ms 12264 KB Output is correct
3 Correct 0 ms 12264 KB Output is correct
4 Correct 6 ms 12264 KB Output is correct
5 Correct 13 ms 12536 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 736 ms 12536 KB Output is correct
2 Correct 416 ms 12536 KB Output is correct
3 Correct 513 ms 12536 KB Output is correct
4 Correct 296 ms 12536 KB Output is correct
5 Correct 663 ms 12732 KB Output is correct
6 Correct 536 ms 12732 KB Output is correct
7 Correct 506 ms 12732 KB Output is correct
8 Correct 349 ms 12732 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 13884 KB Output is correct
2 Correct 126 ms 13884 KB Output is correct
3 Correct 83 ms 13884 KB Output is correct
4 Correct 3 ms 12264 KB Output is correct
5 Correct 216 ms 15420 KB Output is correct
6 Correct 193 ms 15420 KB Output is correct
7 Correct 133 ms 15420 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 12404 KB Output is correct
2 Correct 43 ms 12404 KB Output is correct
3 Correct 103 ms 13116 KB Output is correct
4 Correct 146 ms 13116 KB Output is correct
5 Correct 179 ms 12264 KB Output is correct
6 Correct 193 ms 13884 KB Output is correct
7 Correct 213 ms 12536 KB Output is correct
8 Correct 259 ms 13884 KB Output is correct
9 Correct 1063 ms 15420 KB Output is correct
10 Correct 573 ms 12264 KB Output is correct
11 Correct 636 ms 12732 KB Output is correct
12 Correct 913 ms 15420 KB Output is correct
13 Correct 896 ms 15420 KB Output is correct