oj.uz

답안 #121796

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
121796 2019-06-27T05:22:17 Z rajarshi_basu 케이크 (CEOI14_cake) C++14
100 / 100
 1432 ms 20788 KB 
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>
#define vv vector

using namespace std;

const int MAXN = 250*1000+10;
int arr[MAXN];
int n;

struct SegTrMax{
	int st[4*MAXN];
	void update(int node,int ss,int se,int i,int val){
		if(i > se or i < ss)return;
		if(ss == se){
			st[node] = val;
			return;
		}
		int mid = (ss+se)/2;
		update(node*2+1,ss,mid,i,val);
		update(node*2+2,mid+1,se,i,val);
		st[node] = max(st[node*2+1],st[node*2+2]);
	}
	inline int get(int node,int ss,int se,int l,int r){
		if(l > se or r < ss)return 0;
		if(l <= ss and se <= r)return st[node];
		int mid = (ss+se)/2;
		return max(get(node*2+1,ss,mid,l,r),get(node*2+2,mid+1,se,l,r));
	}
	inline int getL(int node,int ss,int se,int r,int mx){
		if(st[node] < mx)return -1;
		if(ss > r){
			return -1;
		}
		if(ss==se)return ss;
		int mid = (ss+se)/2;
		int x = getL(node*2+2,mid+1,se,r,mx);
		if(x == -1)return getL(node*2+1,ss,mid,r,mx);
		return x;
	}
	inline int getR(int node,int ss,int se,int l,int mx){
		if(st[node] < mx)return n;

		if(se < l){
			return n;
		}
		//cout << ss << " " << se << " " << st[node] << endl;
		if(ss==se)return ss;
		int mid = (ss+se)/2;
		int x = getR(node*2+1,ss,mid,l,mx);
		if(x == n)return getR(node*2+2,mid+1,se,l,mx);
		return x;
	}
};	
set<pair<ll,int>,greater<pair<ll,int> > > st;
#define endl '\n'
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int a;
	cin >> n >> a;
	a--;
	SegTrMax stm;
	FOR(i,n){
		cin >> arr[i];
		stm.update(0,0,MAXN,i,arr[i]);
		st.insert({arr[i],i});
	}
	int q;
	cin >> q;
	while(q--){
		/*
		FOR(i,n)cout << arr[i] << " ";cout << endl;
		for(auto e : st)cout << e.ss+1 << " ";cout << endl;
		cout << endl;*/
		char c;
		cin >> c;
		if(c == 'E'){
			int i,e;
			cin >> i >> e;
			i--;
			st.erase({arr[i],i});
			if(e == 1){
				st.insert({(*st.begin()).ff+1,i});

				arr[i] = (*st.begin()).ff;
				stm.update(0,0,MAXN,i,arr[i]);
				continue;	
			}
			vector<pair<ll,int> > v;
			FOR(i,e-1){
				v.pb(*st.begin());
				st.erase(*st.begin());
			}
			//cout << "got till here" << endl;
			st.insert({v.back().ff,i});
			arr[i] = v.back().ff;
			stm.update(0,0,MAXN,i,arr[i]);
			for(auto e: v){
				st.insert({e.ff+1,e.ss});
				arr[e.ss] = e.ff+1;
				stm.update(0,0,MAXN,e.ss,arr[e.ss]);
			}
		}else{
			int b;
			cin >> b;
			b--;
			if(b == a)cout << 0 << endl;
			else if(b < a){
				int mx = stm.get(0,0,MAXN,b,a-1);
				int c = stm.getR(0,0,MAXN,a+1,mx);
				cout << c - b - 1 << endl;
			}else{
				int mx = stm.get(0,0,MAXN,a+1,b);
				int c = stm.getL(0,0,MAXN,a-1,mx);
				cout << b - c - 1 << endl;
			}
		}
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 9 ms 384 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 21 ms 1152 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 636 ms 1120 KB Output is correct
2 Correct 337 ms 1152 KB Output is correct
3 Correct 430 ms 1192 KB Output is correct
4 Correct 265 ms 1272 KB Output is correct
5 Correct 736 ms 2304 KB Output is correct
6 Correct 687 ms 2424 KB Output is correct
7 Correct 477 ms 2324 KB Output is correct
8 Correct 307 ms 2304 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 8596 KB Output is correct
2 Correct 99 ms 8444 KB Output is correct
3 Correct 90 ms 8288 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 331 ms 19832 KB Output is correct
6 Correct 553 ms 19648 KB Output is correct
7 Correct 163 ms 19448 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 760 KB Output is correct
2 Correct 45 ms 1016 KB Output is correct
3 Correct 128 ms 4344 KB Output is correct
4 Correct 159 ms 4344 KB Output is correct
5 Correct 182 ms 888 KB Output is correct
6 Correct 224 ms 5756 KB Output is correct
7 Correct 173 ms 1656 KB Output is correct
8 Correct 331 ms 8024 KB Output is correct
9 Correct 1400 ms 20776 KB Output is correct
10 Correct 608 ms 1700 KB Output is correct
11 Correct 805 ms 3348 KB Output is correct
12 Correct 1432 ms 16908 KB Output is correct
13 Correct 988 ms 20788 KB Output is correct