oj.uz

답안 #30139

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30139 2017-07-22T08:02:30 Z cdemirer 케이크 (CEOI14_cake) C++14
51.6667 / 100
 2000 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 if (topten.size() > 0) topten.insert(topten.begin()+b-1, mp(topten[b-1].first+1, a));
	//else topten.insert(topten.begin()+b-1, mp(1, a));
	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);
}

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:171: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:177: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:197:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
cake.cpp:199:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%c", &t);
                 ^
cake.cpp:201:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &t);
                  ^
cake.cpp:203: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:212: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:232: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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12264 KB Output is correct
2 Correct 3 ms 12264 KB Output is correct
3 Correct 0 ms 12264 KB Output is correct
4 Correct 19 ms 12264 KB Output is correct
5 Correct 46 ms 12536 KB Output is correct

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 493 ms 12536 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 206 ms 12536 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 309 ms 12536 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 173 ms 12536 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 456 ms 12732 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 323 ms 12732 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 459 ms 12732 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 209 ms 12732 KB Execution timed out (wall clock limit exceeded)

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 13884 KB Output is correct
2 Correct 126 ms 13884 KB Output is correct
3 Correct 96 ms 13884 KB Output is correct
4 Correct 6 ms 12264 KB Output is correct
5 Correct 196 ms 15420 KB Output is correct
6 Correct 206 ms 15420 KB Output is correct
7 Correct 129 ms 15420 KB Output is correct

Subtask #4
16.666667 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 429 ms 12404 KB Output is correct
2 Correct 373 ms 12404 KB Output is correct
3 Correct 1276 ms 13116 KB Output is correct
4 Correct 1349 ms 13116 KB Output is correct
5 Runtime error 366 ms 12264 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 1783 ms 13884 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 713 ms 12536 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 906 ms 13884 KB Execution timed out (wall clock limit exceeded)
9 Execution timed out 2000 ms 0 KB Execution timed out
10 Runtime error 483 ms 12264 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 886 ms 12732 KB Execution timed out (wall clock limit exceeded)
12 Execution timed out 2000 ms 15420 KB Execution timed out
13 Runtime error 583 ms 15420 KB Execution timed out (wall clock limit exceeded)