oj.uz

답안 #121785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
121785 2019-06-27T05:00:51 Z rajarshi_basu 케이크 (CEOI14_cake) C++14
46.6667 / 100
 2000 ms 18512 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;
inline ll getMax(int l,int r){
	int mx = 0;
	FORE(i,l,r)mx = max(mx,arr[i]);
	return mx;
}
inline int getFirst(int a,int mx){
	while(a < n){
		if(arr[a] > mx)return a;
		a++;
	}
	return a;
}
inline int getFirst2(int a,int mx){
	while(a > -1){
		if(arr[a] > mx)return a;
		a--;
	}
	return a;
}

int findCnt(int a,int b){
	int ptr1 = a;
	int ptr2 = a;
	int cnt = 0;
	if(a == b)return 0;
	ptr1 = a-1;
	ptr2 = a+1;
	cnt = 1;
	while(1){
		//cout << ptr1 << " " << ptr2 << endl;
		if(ptr1 == b-1 or ptr2 == b+1)return cnt-1;
		if(ptr2 == n)ptr1--;
		else if(ptr1 == -1)ptr2++;
		else if(arr[ptr2] < arr[ptr1])ptr2++;//,cout << "boo1" << endl;
		else ptr1--;//,cout << "boo2" << endl;

		cnt++;
	}
	//cout << endl;
}

set<pair<ll,int>,greater<pair<ll,int> > > st;
int main(){
	int a;
	cin >> n >> a;
	a--;
	FOR(i,n){
		cin >> 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;
				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;
			for(auto e: v){
				st.insert({e.ff+1,e.ss});
				arr[e.ss] = e.ff+1;
			}
		}else{
			int b;
			cin >> b;
			b--;
			//cout << b << " " << a << endl;
			//cout << findCnt(a,b) << endl;
			//continue;
			if(b == a)cout << 0 << endl;
			else if(b < a){
				int mx = getMax(b,a-1);
				int c = getFirst(a+1,mx);
				cout << c - b - 1 << endl;
			}else{
				int mx = getMax(a+1,b);
				int c = getFirst2(a-1,mx);
				cout << b - c - 1 << endl;
			}
		}
	}
	return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 639 ms 1760 KB Output is correct
2 Correct 429 ms 1912 KB Output is correct
3 Correct 504 ms 1788 KB Output is correct
4 Correct 391 ms 1784 KB Output is correct
5 Correct 751 ms 2808 KB Output is correct
6 Correct 642 ms 2808 KB Output is correct
7 Correct 525 ms 2808 KB Output is correct
8 Correct 436 ms 2940 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2044 ms 8508 KB Time limit exceeded
2 Execution timed out 2047 ms 8860 KB Time limit exceeded
3 Execution timed out 2040 ms 8804 KB Time limit exceeded
4 Correct 2 ms 384 KB Output is correct
5 Execution timed out 2045 ms 18312 KB Time limit exceeded
6 Execution timed out 2062 ms 18324 KB Time limit exceeded
7 Execution timed out 2058 ms 18512 KB Time limit exceeded

Subtask #4
16.666667 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 1020 KB Output is correct
2 Correct 122 ms 1144 KB Output is correct
3 Correct 911 ms 4888 KB Output is correct
4 Correct 892 ms 5000 KB Output is correct
5 Correct 299 ms 1740 KB Output is correct
6 Execution timed out 2050 ms 6392 KB Time limit exceeded
7 Correct 691 ms 2560 KB Output is correct
8 Correct 439 ms 7932 KB Output is correct
9 Execution timed out 2044 ms 18248 KB Time limit exceeded
10 Correct 993 ms 2680 KB Output is correct
11 Execution timed out 2052 ms 4076 KB Time limit exceeded
12 Execution timed out 2054 ms 14932 KB Time limit exceeded
13 Execution timed out 2053 ms 18280 KB Time limit exceeded