oj.uz

답안 #29874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29874 2017-07-21T09:47:57 Z cdemirer 케이크 (CEOI14_cake) C++14
35 / 100
 2000 ms 19468 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;
vii topten;
int maxcumul[250000];

vii addtt(int a, int b) {
	vii changelog;
	bool erased = false;
	for (int i = 0; i < topten.size(); i++) {
		if (topten[i].second == a) {
			topten.erase(topten.begin()+i);
			erased = true;
			break;
		}
	}
	if (!erased) {
		topten.erase(topten.begin()+topten.size()-1);
	}
	for (int i = 0; i < b-1; i++) {
		topten[i].first++;
		changelog.pb(mp(topten[i].second, topten[i].first));
	}
	int d;
	if (b != topten.size()+1) d = topten[b-1].first+1;
	else d = topten[b-2].first-1;
	topten.insert(topten.begin()+b-1, mp(d, a));
	changelog.pb(mp(a, d));
	return changelog;
}

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;
}

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

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

	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));
			arr.pb(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);
	}
	/*for (int i = 1; i < N; i++) {
		cerr << lbitget(i) << endl;
	}*/
	sort(arr.begin(), arr.end());
	reverse(arr.begin(), arr.end());
	for (int i = 0; i < arr.size(); i++) {
		topten.pb(arr[i]);
	}
	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--;
			vii ch = addtt(a, b);
			for (int i = 0; i < ch.size(); i++) {
				change(1, ch[i].first, ch[i].second);
				if (ch[i].first < A) {
					lbitmax(A-ch[i].first, ch[i].second);
				}
				if (ch[i].first > A) {
					rbitmax(ch[i].first-A, ch[i].second);
				}
			}
			/*for (int i = 0; i < N; i++) {
				cerr << seg[i+offset].vmax << " ";
			}
			cerr << endl;*/
		}
		else if (t == 'F') {
			int a; scanf("%d", &a);
			a--;
			//printf("a: %d\n", a);
			if (a == A) {
				printf("0\n");
			}
			else if (a > A) {
				int m = get(1, A+1, a);
				int lp = lbin(m);
				//printf("lp a : %d %d", lp, a);
				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 'vii addtt(int, int)':
cake.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < topten.size(); i++) {
                    ^
cake.cpp:81:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (b != topten.size()+1) d = topten[b-1].first+1;
        ^
cake.cpp: In function 'int main(int, char**)':
cake.cpp:169:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size(); i++) {
                    ^
cake.cpp:181:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < ch.size(); i++) {
                      ^
cake.cpp:142: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:148: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:172:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
cake.cpp:174:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%c", &t);
                 ^
cake.cpp:176:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &t);
                  ^
cake.cpp:178: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:196: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:218: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 0 ms 13240 KB Output is correct
2 Correct 0 ms 13240 KB Output is correct
3 Correct 3 ms 13240 KB Output is correct
4 Correct 13 ms 13240 KB Output is correct
5 Correct 119 ms 13580 KB Output is correct

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2000 ms 13580 KB Execution timed out
2 Execution timed out 2000 ms 13580 KB Execution timed out
3 Execution timed out 2000 ms 13580 KB Execution timed out
4 Execution timed out 2000 ms 13580 KB Execution timed out
5 Execution timed out 2000 ms 14092 KB Execution timed out
6 Execution timed out 2000 ms 14092 KB Execution timed out
7 Execution timed out 2000 ms 14092 KB Execution timed out
8 Execution timed out 2000 ms 14092 KB Execution timed out

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 16396 KB Output is correct
2 Correct 119 ms 16396 KB Output is correct
3 Correct 136 ms 16396 KB Output is correct
4 Correct 0 ms 13240 KB Output is correct
5 Correct 229 ms 19468 KB Output is correct
6 Correct 203 ms 19468 KB Output is correct
7 Correct 183 ms 19468 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 13380 KB Output is correct
2 Correct 329 ms 13380 KB Output is correct
3 Execution timed out 2000 ms 14860 KB Execution timed out
4 Execution timed out 2000 ms 14860 KB Execution timed out
5 Correct 503 ms 13240 KB Output is correct
6 Execution timed out 2000 ms 16396 KB Execution timed out
7 Execution timed out 2000 ms 13580 KB Execution timed out
8 Execution timed out 2000 ms 16396 KB Execution timed out
9 Execution timed out 2000 ms 19468 KB Execution timed out
10 Correct 1663 ms 13240 KB Output is correct
11 Execution timed out 2000 ms 14092 KB Execution timed out
12 Execution timed out 2000 ms 19468 KB Execution timed out
13 Execution timed out 2000 ms 19468 KB Execution timed out