oj.uz

Submission #121787

# Submission time Handle Problem Language Result Execution time Memory
121787 2019-06-27T05:05:54 Z rajarshi_basu Cake (CEOI14_cake) C++14
63.3333 / 100
 2000 ms 20320 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]);
	}
	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 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--;
	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 = getFirst(a+1,mx);
				cout << c - b - 1 << endl;
			}else{
				int mx = stm.get(0,0,MAXN,a+1,b);
				int c = getFirst2(a-1,mx);
				cout << b - c - 1 << endl;
			}
		}
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 14 ms 512 KB Output is correct
5 Correct 41 ms 1280 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 1272 KB Output is correct
2 Correct 528 ms 1404 KB Output is correct
3 Correct 618 ms 1396 KB Output is correct
4 Correct 449 ms 1400 KB Output is correct
5 Correct 995 ms 2400 KB Output is correct
6 Correct 858 ms 2424 KB Output is correct
7 Correct 701 ms 2416 KB Output is correct
8 Correct 507 ms 2552 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1876 ms 9112 KB Output is correct
2 Correct 1647 ms 8596 KB Output is correct
3 Execution timed out 2051 ms 8732 KB Time limit exceeded
4 Correct 2 ms 384 KB Output is correct
5 Execution timed out 2047 ms 19816 KB Time limit exceeded
6 Execution timed out 2071 ms 19784 KB Time limit exceeded
7 Execution timed out 2051 ms 19576 KB Time limit exceeded

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 1016 KB Output is correct
2 Correct 118 ms 988 KB Output is correct
3 Correct 563 ms 4600 KB Output is correct
4 Correct 591 ms 4472 KB Output is correct
5 Correct 342 ms 1236 KB Output is correct
6 Correct 1253 ms 6100 KB Output is correct
7 Correct 556 ms 1984 KB Output is correct
8 Correct 469 ms 8056 KB Output is correct
9 Execution timed out 2061 ms 19964 KB Time limit exceeded
10 Correct 1166 ms 2472 KB Output is correct
11 Execution timed out 2054 ms 4596 KB Time limit exceeded
12 Execution timed out 2065 ms 16680 KB Time limit exceeded
13 Execution timed out 2033 ms 20320 KB Time limit exceeded