oj.uz

답안 #114114

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114114 2019-05-30T11:57:28 Z dndhk 케이크 (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 15412 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++){
		string str;
		cin>>str;
		if(str[0]=='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:147:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~
cake.cpp:151: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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 18 ms 512 KB Output is correct
5 Correct 29 ms 892 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 569 ms 5124 KB Output is correct
2 Correct 534 ms 5276 KB Output is correct
3 Correct 555 ms 5252 KB Output is correct
4 Correct 517 ms 5268 KB Output is correct
5 Correct 656 ms 5860 KB Output is correct
6 Correct 622 ms 6368 KB Output is correct
7 Correct 640 ms 6080 KB Output is correct
8 Correct 572 ms 6268 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 594 ms 5272 KB Output is correct
2 Correct 469 ms 5128 KB Output is correct
3 Correct 459 ms 5104 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 653 ms 10588 KB Output is correct
6 Correct 677 ms 10428 KB Output is correct
7 Correct 597 ms 10328 KB Output is correct

Subtask #4
33.333333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 988 KB Output is correct
2 Correct 132 ms 1308 KB Output is correct
3 Correct 290 ms 3100 KB Output is correct
4 Correct 243 ms 3048 KB Output is correct
5 Correct 299 ms 1912 KB Output is correct
6 Correct 562 ms 4324 KB Output is correct
7 Correct 474 ms 2804 KB Output is correct
8 Correct 330 ms 5732 KB Output is correct
9 Execution timed out 2041 ms 15180 KB Time limit exceeded
10 Correct 1014 ms 5368 KB Output is correct
11 Correct 1340 ms 6824 KB Output is correct
12 Execution timed out 2057 ms 13500 KB Time limit exceeded
13 Execution timed out 2063 ms 15412 KB Time limit exceeded