oj.uz

답안 #346029

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
346029 2021-01-09T04:00:30 Z kym 케이크 (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 57396 KB 
#include <bits/stdc++.h>
using namespace std;
#define int ll 
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#else
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
#define reach cerr << "LINE: " << __LINE__ << "\n";
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
typedef tuple<ll,ll,ll,ll> ti4;
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 250005;
int A[MAXN], D[MAXN], n, st;
int qq = 1;

struct node {
	int s,e,m,val;
	node *l, *r;
	node(int _s, int _e){
		s=_s,e=_e;
		m=(s+e)/2;
		val=0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void set(int x, int nval) {
		if(s==e){
			val=nval;
			return;
		}
		if(x>m)r->set(x,nval);
		else l->set(x,nval);
		val=max(l->val,r->val);
	}
	void add(int x, int nval) {
		if(s==e){
			val+=nval;
			return;
		}
		if(x>m)r->add(x,nval);
		else l->add(x,nval);
		val=max(l->val,r->val);
	}
	int query(int x, int y) {
		if(s==x&&e==y) {
			return val;
		}
		if(x>m)return r->query(x,y);
		else if(y<=m)return l->query(x,y);
		else return max(l->query(x,m), r->query(m+1,y));
	}
} *seg;

int32_t main() 
{
	IAMSPEED
	cin >> n >> st;
	seg=new node(0,n);
	set<pi,greater<pi>> s;
	FOR(i,1,n) {
		int x; cin >> x;
		x*=2;
		//x=n-x+1;
		A[i]=x;
		seg->set(i,x);
		s.insert(pi(x,i));
	}
	
	int Q; cin >> Q;	
	while(Q--) {
		//dba(A,1,n);
		
		char op; cin >> op;
		if(op == 'E') {
			int x, e; cin >> x >> e;
			
			int cnt = 1;
			auto it = s.begin();
			while(cnt < e) {
				seg->add(it->s, 1);
				A[it->s]++;
				pi npair = *it;
				s.insert(pi(npair.f+1,npair.s));
				s.erase(it);
				it=s.lower_bound(pi(npair.f+1,npair.s));
				it=next(it);
				++cnt;
			}
			int nval = it->f+1;
			seg->set(x, nval);
			s.erase(s.find(pi(A[x], x)));
			s.insert(pi(nval,x));
			A[x]=nval;
		} else {
			int x; cin >> x;
			if(x==st){
				cout << 0 << '\n'; continue;
			}
			if(x>st){
				int mx=seg->query(st+1,x);
				int lo = 0, hi = st;
				while(lo < hi -1) {
					int mid=(lo+hi)/2;
					if(seg->query(mid,st-1) > mx)lo=mid;
					else hi=mid;
				}
				cout << x-lo-1 << '\n';
			} else {
				int mx=seg->query(x,st-1);
				//db2(x,st-1);
				//db2(seg->query(1,1),seg->query(2,2));
				//db(mx);
				int lo = st, hi=n+1;
				while (lo<hi-1){
					int mid=(lo+hi)/2;
					if(seg->query(st+1,mid)>mx)hi=mid;
					else lo=mid;
				}
				//db(hi);
				cout << hi-x-1 << '\n';
			}
		}
		++qq;
	}
}


//g++ -std=c++17 -DLOCAL -Wall -Wshadow -static -O2 -lm -s -w -std=gnu++17 -fmax-errors=512 -o "%e" "%f" 
//g++ -std=c++17 -DLOCAL -O2 -Wall -Wl,--stack=268435456 -o "%e" "%f"

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 8 ms 620 KB Output is correct
5 Correct 27 ms 2540 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 640 ms 6652 KB Output is correct
2 Correct 312 ms 6764 KB Output is correct
3 Correct 414 ms 6764 KB Output is correct
4 Correct 232 ms 6764 KB Output is correct
5 Correct 759 ms 9964 KB Output is correct
6 Correct 578 ms 10348 KB Output is correct
7 Correct 478 ms 10092 KB Output is correct
8 Correct 279 ms 10604 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 418 ms 21996 KB Output is correct
2 Correct 267 ms 21868 KB Output is correct
3 Correct 272 ms 21740 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 664 ms 52460 KB Output is correct
6 Correct 623 ms 52460 KB Output is correct
7 Correct 387 ms 52204 KB Output is correct

Subtask #4
33.333333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 1516 KB Output is correct
2 Correct 73 ms 1900 KB Output is correct
3 Correct 259 ms 11244 KB Output is correct
4 Correct 277 ms 11276 KB Output is correct
5 Correct 226 ms 2156 KB Output is correct
6 Correct 538 ms 15372 KB Output is correct
7 Correct 299 ms 4588 KB Output is correct
8 Correct 359 ms 22464 KB Output is correct
9 Execution timed out 2088 ms 56140 KB Time limit exceeded
10 Correct 749 ms 5740 KB Output is correct
11 Correct 1201 ms 9964 KB Output is correct
12 Execution timed out 2070 ms 46428 KB Time limit exceeded
13 Correct 1902 ms 57396 KB Output is correct