oj.uz

답안 #25941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25941 2017-06-25T07:31:42 Z 김현수(#1087) 케이크 (CEOI14_cake) C++11
0 / 100
 453 ms 13984 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 250005;

ll n, s, q, a[N], sz, li[N];
bool in[N];

struct segtree {
	ll val[4*N], lim;
	void init () {
		for(lim=1;lim<=n+1;lim<<=1);
		for(ll i=1;i<=n;i++) val[lim+i] = a[i];
		for(ll i=lim;--i;) val[i] = max(val[2*i], val[2*i+1]);
	}
	void upd (ll P, ll V) {
		P += lim;
		while(P) {val[P] = max(val[P], V); P >>= 1;}
	}
	ll get (ll S, ll E) {
		ll R = 0; S += lim; E += lim;
		while(S <= E) {
			if(S%2==1) {R = max(R, val[S]); S++;}
			if(E%2==0) {R = max(R, val[E]); E--;}
			S>>=1; E>>=1;
		}
		return R;
	}
	ll lb (ll P, ll X) {
		P += lim;
		while(P&(P+1)) {
			if(val[P] >= X) break;
			P = (P-1)/2;
		}
		if(!(P&(P+1))) return 0;
		while(P < lim) {
			if(val[2*P+1] >= X) P = 2*P+1;
			else P = 2*P;
		}
		return P - lim;
	}
	ll rb (ll P, ll X) {
		P += lim;
		while(P&(P-1)) {
			if(val[P] >= X) break;
			P = (P+1)/2;
		}
		if(!(P&(P-1))) return n+1;
		while(P < lim) {
			if(val[2*P] >= X) P = 2*P;
			else P = 2*P+1;
		}
		return P - lim;
	}
} seg;

int main()
{
	scanf("%lld%lld",&n,&s);
	sz = min(10ll, n);
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		if(a[i] > n-sz) {
			li[n-a[i]] = i;
			in[i] = true;
		}
	}
	seg.init();
	scanf("%lld",&q);
	while(q--) {
		char typ[2];
		scanf("%s",typ);
		if(typ[0] == 'F') {
			ll P, V;
			scanf("%lld",&P);
			if(P == s) puts("0");
			else if(P < s) {
				V = seg.get(P, s-1);
				printf("%lld\n", seg.rb(s+1, V)-P-1);
			}
			else if(P > s) {
				V = seg.get(s+1, P);
				printf("%lld\n", P-seg.lb(s-1, V)-1);
			}
		}
		else {
			ll P, Q;
			vector<ll> T;
			scanf("%lld%lld",&P,&Q);
			for(ll i=0;i<Q-1;i++) {
				a[li[i]]++;
				seg.upd(li[i], a[li[i]]);
			}
			a[P] = a[li[Q-1]]+1;
			seg.upd(P, a[P]);
			li[sz] = (in[P] ? 0 : P);
			for(ll i=sz;i;i--) {
				if(a[li[i-1]] < a[li[i]]) {
					swap(li[i-1], li[i]);
				}
			}
			in[li[sz]] = false;
		}
	}
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:60:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&s);
                         ^
cake.cpp:63:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^
cake.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&q);
                  ^
cake.cpp:73:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",typ);
                  ^
cake.cpp:76:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&P);
                    ^
cake.cpp:90:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld",&P,&Q);
                           ^

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 13984 KB Output is correct
2 Incorrect 0 ms 13984 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 229 ms 13984 KB Output isn't correct
2 Correct 229 ms 13984 KB Output is correct
3 Incorrect 183 ms 13984 KB Output isn't correct
4 Correct 143 ms 13984 KB Output is correct
5 Incorrect 219 ms 13984 KB Output isn't correct
6 Incorrect 219 ms 13984 KB Output isn't correct
7 Incorrect 239 ms 13984 KB Output isn't correct
8 Correct 143 ms 13984 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 13984 KB Output is correct
2 Incorrect 49 ms 13984 KB Output isn't correct
3 Correct 49 ms 13984 KB Output is correct
4 Correct 0 ms 13984 KB Output is correct
5 Correct 109 ms 13984 KB Output is correct
6 Incorrect 83 ms 13984 KB Output isn't correct
7 Correct 89 ms 13984 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 13984 KB Output isn't correct
2 Incorrect 19 ms 13984 KB Output isn't correct
3 Correct 46 ms 13984 KB Output is correct
4 Incorrect 63 ms 13984 KB Output isn't correct
5 Incorrect 63 ms 13984 KB Output isn't correct
6 Incorrect 96 ms 13984 KB Output isn't correct
7 Incorrect 79 ms 13984 KB Output isn't correct
8 Incorrect 123 ms 13984 KB Output isn't correct
9 Incorrect 453 ms 13984 KB Output isn't correct
10 Incorrect 269 ms 13984 KB Output isn't correct
11 Incorrect 309 ms 13984 KB Output isn't correct
12 Incorrect 429 ms 13984 KB Output isn't correct
13 Incorrect 386 ms 13984 KB Output isn't correct