oj.uz

Submission #29907

# Submission time Handle Problem Language Result Execution time Memory
29907 2017-07-21T10:23:00 Z cdemirer Cake (CEOI14_cake) C++14
20 / 100
 2000 ms 24992 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;
set<ii> S;
int maxcumul[250000];

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);
	}
	if (S.size() >= b) it++;
	else it = S.begin();
	ii qw;
	if (it == S.end()) {it--; if(S.size() != 0) qw = mp((*it).first+1, a); else qw = mp(1, a);}
	else 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) {
			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++;
		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);
		}
	}
	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));
	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));
			//arr.pb(mp(seg[i].vmax, i-offset));
			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);
	}
	/*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--;
			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--;
			//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 'void addtt(int, int)':
cake.cpp:129:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (S.size() >= b) it++;
               ^
cake.cpp: In function 'int main(int, char**)':
cake.cpp:179: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:185: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:210:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
cake.cpp:212:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%c", &t);
                 ^
cake.cpp:214:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &t);
                  ^
cake.cpp:216: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:225: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:247: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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13244 KB Output is correct
2 Correct 26 ms 13244 KB Output is correct
3 Runtime error 63 ms 13244 KB Execution timed out (wall clock limit exceeded)
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 13640 KB Execution timed out (wall clock limit exceeded)
2 Execution timed out 2000 ms 13772 KB Execution timed out
3 Execution timed out 2000 ms 13772 KB Execution timed out
4 Execution timed out 2000 ms 13772 KB Execution timed out
5 Execution timed out 2000 ms 14432 KB Execution timed out
6 Execution timed out 2000 ms 14432 KB Execution timed out
7 Execution timed out 2000 ms 14432 KB Execution timed out
8 Execution timed out 2000 ms 14432 KB Execution timed out

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 17996 KB Output is correct
2 Correct 639 ms 17996 KB Output is correct
3 Correct 599 ms 17996 KB Output is correct
4 Correct 0 ms 13244 KB Output is correct
5 Correct 1423 ms 24992 KB Output is correct
6 Correct 1629 ms 24992 KB Output is correct
7 Correct 1279 ms 24992 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 13376 KB Execution timed out
2 Execution timed out 2000 ms 13508 KB Execution timed out
3 Execution timed out 2000 ms 15620 KB Execution timed out
4 Execution timed out 2000 ms 15620 KB Execution timed out
5 Execution timed out 2000 ms 13376 KB Execution timed out
6 Execution timed out 2000 ms 16280 KB Execution timed out
7 Execution timed out 2000 ms 13772 KB Execution timed out
8 Execution timed out 2000 ms 17996 KB Execution timed out
9 Execution timed out 2000 ms 24992 KB Execution timed out
10 Execution timed out 2000 ms 13376 KB Execution timed out
11 Execution timed out 2000 ms 14168 KB Execution timed out
12 Execution timed out 2000 ms 22616 KB Execution timed out
13 Execution timed out 2000 ms 24992 KB Execution timed out