oj.uz

Submission #25943

# Submission time Handle Problem Language Result Execution time Memory
25943 2017-06-25T07:36:48 Z 김현수(#1087) Cake (CEOI14_cake) C++11
0 / 100
 466 ms 12028 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[15];
bool in[N];

struct segtree {
	ll val[4*N], lim;
	void init () {
		for(lim=1;lim<=N;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]+1] = 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;
			scanf("%lld%lld",&P,&Q);
			for(ll i=1;i<Q;i++) {
				a[li[i]]++;
				seg.upd(li[i], a[li[i]]);
			}
			a[P] = a[li[Q]]+1;
			seg.upd(P, a[P]);
			li[sz+1] = (in[P] ? 0 : P);
			for(ll i=sz;i;i--) {
				if(a[li[i]] < a[li[i+1]]) {
					swap(li[i], li[i+1]);
				}
			}
			in[li[sz]] = false;
			in[P] = true;
		}
	}
}

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:89: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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12028 KB Output is correct
2 Incorrect 0 ms 12028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 12028 KB Output isn't correct
2 Correct 219 ms 12028 KB Output is correct
3 Correct 256 ms 12028 KB Output is correct
4 Correct 169 ms 12028 KB Output is correct
5 Incorrect 266 ms 12028 KB Output isn't correct
6 Correct 183 ms 12028 KB Output is correct
7 Correct 189 ms 12028 KB Output is correct
8 Correct 203 ms 12028 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12028 KB Output is correct
2 Incorrect 76 ms 12028 KB Output isn't correct
3 Correct 69 ms 12028 KB Output is correct
4 Correct 0 ms 12028 KB Output is correct
5 Correct 116 ms 12028 KB Output is correct
6 Incorrect 86 ms 12028 KB Output isn't correct
7 Correct 89 ms 12028 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 12028 KB Output isn't correct
2 Incorrect 26 ms 12028 KB Output isn't correct
3 Correct 49 ms 12028 KB Output is correct
4 Incorrect 53 ms 12028 KB Output isn't correct
5 Incorrect 83 ms 12028 KB Output isn't correct
6 Correct 69 ms 12028 KB Output is correct
7 Incorrect 96 ms 12028 KB Output isn't correct
8 Correct 113 ms 12028 KB Output is correct
9 Incorrect 466 ms 12028 KB Output isn't correct
10 Incorrect 286 ms 12028 KB Output isn't correct
11 Incorrect 289 ms 12028 KB Output isn't correct
12 Incorrect 409 ms 12028 KB Output isn't correct
13 Incorrect 326 ms 12028 KB Output isn't correct