oj.uz

Submission #114115

# Submission time Handle Problem Language Result Execution time Memory
114115 2019-05-30T12:00:00 Z dndhk Cake (CEOI14_cake) C++14
100 / 100
 1688 ms 9200 KB 
#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 250000;

int N, C, Q;
int arr[MAX_N+1];
vector<int> v;

struct SEG{
	SEG(int l, int r, int mx) : l(l), r(r), mx(mx) {}
	int l, r;
	int mx;
};

vector<SEG> seg;

void init(int idx, int s, int e){
	if(s==e)	return;
	seg[idx].l = seg.size(); seg.pb({-1, -1, 0});
	seg[idx].r = seg.size(); seg.pb({-1, -1, 0});
	init(seg[idx].l, s, (s+e)/2);
	init(seg[idx].r, (s+e)/2+1, e);
}

void update(int idx, int s, int e, int x, int y){
	if(s==e){
		seg[idx].mx = y;
		return;
	}
	if(x<=(s+e)/2){
		update(seg[idx].l, s, (s+e)/2, x, y);
	}else{
		update(seg[idx].r, (s+e)/2+1, e, x, y);
	}
	seg[idx].mx = max(seg[seg[idx].l].mx, seg[seg[idx].r].mx);
}

int max(int idx, int s, int e, int x, int y){
	if(x<=s && e<=y)	return seg[idx].mx;
	if(x>e || s>y)	return 0;
	return max(max(seg[idx].l, s, (s+e)/2, x, y), max(seg[idx].r, (s+e)/2+1, e, x, y));
}

int ans(int x){
	if(C==x)	return 0;
	if(x>C){
		int t = max(0, 1, N, C+1, x);
		int s = 1, e = C, m;
		while(s<e){
			m = (s+e)/2;
			if(max(0, 1, N, m, C-1)>t){
				s = m+1;
			}else{
				e = m;
			}
		}
		return x - s;
	}else{
		int t = max(0, 1, N, x, C-1);
		//cout<<t<<endl;
		int s = C, e = N, m;
		while(s<e){
			m = (s+e)/2+1;
			if(max(0, 1, N, C+1, m)>t){
				e = m-1;
			}else{
				s = m;
			}
		}
		return s - x;
	}
}

int maxarr;

void change(int x, int y){
	y--;
	int idx = -1;
	for(int i=0; i<v.size(); i++){
		if(v[i]==x){
			idx = i;
			break;
		}
	}
	if(idx==-1){
		for(int i=v.size(); i>=y+1; i--){
			v[i] = v[i-1];
		}
		v[y] = x;
	}else{
		for(int j=idx; j>=y+1; j--){
			v[j] = v[j-1];
		}
		v[y] = x;
	}
	for(int i=0; i<v.size(); i++){
		update(0, 1, N, v[i], maxarr+10-i);
	}
	maxarr += 10;
}


int main(){
	seg.pb({-1, -1, 0});
	scanf("%d%d", &N, &C);
	init(0, 1, N);
	maxarr = N;
	for(int i=1; i<=N; i++){
		scanf("%d", &arr[i]);
		update(0, 1, N, i, arr[i]);
	}
	for(int i=N; i>=max(1, N-9); i--){
		for(int j=1; j<=N; j++){
			if(arr[j]==i){
				v.pb(j);
				break;
			}
		}
	}
	scanf("%d", &Q);
	for(int i=0; i<Q; i++){
		getchar();
		char c;
		scanf("%c", &c);
		if(c=='F'){
			int x;
			scanf("%d", &x);
			printf("%d\n", ans(x));
		}else{
			int x, y;
			scanf("%d%d", &x, &y);
			change(x, y);
		}
	}
	return 0;
}

Compilation message

cake.cpp: In function 'void change(int, int)':
cake.cpp:100:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
cake.cpp:117:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
cake.cpp: In function 'int main()':
cake.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &C);
  ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~
cake.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
cake.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &c);
   ~~~~~^~~~~~~~~~
cake.cpp:148:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~
cake.cpp:152:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &x, &y);
    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 384 KB Output is correct
5 Correct 22 ms 832 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 832 KB Output is correct
2 Correct 492 ms 832 KB Output is correct
3 Correct 510 ms 832 KB Output is correct
4 Correct 457 ms 832 KB Output is correct
5 Correct 650 ms 1276 KB Output is correct
6 Correct 547 ms 1276 KB Output is correct
7 Correct 556 ms 1276 KB Output is correct
8 Correct 517 ms 1276 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 3832 KB Output is correct
2 Correct 321 ms 3668 KB Output is correct
3 Correct 321 ms 3704 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 503 ms 8024 KB Output is correct
6 Correct 535 ms 8024 KB Output is correct
7 Correct 486 ms 7740 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 632 KB Output is correct
2 Correct 90 ms 704 KB Output is correct
3 Correct 219 ms 2040 KB Output is correct
4 Correct 192 ms 2040 KB Output is correct
5 Correct 190 ms 888 KB Output is correct
6 Correct 443 ms 3700 KB Output is correct
7 Correct 311 ms 1268 KB Output is correct
8 Correct 302 ms 3568 KB Output is correct
9 Correct 1684 ms 9176 KB Output is correct
10 Correct 614 ms 1656 KB Output is correct
11 Correct 895 ms 2452 KB Output is correct
12 Correct 1587 ms 7716 KB Output is correct
13 Correct 1688 ms 9200 KB Output is correct