oj.uz

Submission #25941

# Submission time Handle Problem Language Result Execution time Memory
25941 2017-06-25T07:31:42 Z 김현수(#1087) Cake (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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