oj.uz

Submission #121791

# Submission time Handle Problem Language Result Execution time Memory
121791 2019-06-27T05:10:15 Z rajarshi_basu Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 24904 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));
	}
	int getL(int node,int ss,int se,int r,int mx){
		if(st[node] < mx)return -1;
		if(ss > r){
			return -1;
		}
		int mid = (ss+se)/2;
		int x = get(node*2+2,mid+1,se,r,mx);
		if(x == -1)return get(node*2+1,ss,mid,r,mx);
		return x;
	}
	int getR(int node,int ss,int se,int l,int mx){
		if(st[node] < mx)return n;
		if(se < l){
			return n;
		}
		int mid = (ss+se)/2;
		int x = get(node*2+1,ss,mid,l,mx);
		if(x == n)return get(node*2+2,mid+1,se,l,mx);
		return x;
	}
};	

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 = 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 839 ms 1532 KB Output isn't correct
2 Incorrect 520 ms 1528 KB Output isn't correct
3 Incorrect 631 ms 1528 KB Output isn't correct
4 Incorrect 441 ms 1528 KB Output isn't correct
5 Incorrect 1002 ms 2680 KB Output isn't correct
6 Incorrect 855 ms 2680 KB Output isn't correct
7 Incorrect 719 ms 2664 KB Output isn't correct
8 Incorrect 517 ms 2680 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 378 ms 8824 KB Output isn't correct
2 Incorrect 292 ms 9012 KB Output isn't correct
3 Incorrect 277 ms 8924 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 592 ms 20804 KB Output isn't correct
6 Incorrect 560 ms 20748 KB Output isn't correct
7 Incorrect 388 ms 20600 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 888 KB Output isn't correct
2 Incorrect 97 ms 1176 KB Output isn't correct
3 Incorrect 238 ms 4504 KB Output isn't correct
4 Incorrect 267 ms 4576 KB Output isn't correct
5 Incorrect 338 ms 1436 KB Output isn't correct
6 Incorrect 438 ms 6264 KB Output isn't correct
7 Incorrect 406 ms 2048 KB Output isn't correct
8 Incorrect 436 ms 8312 KB Output isn't correct
9 Execution timed out 2057 ms 24904 KB Time limit exceeded
10 Incorrect 1090 ms 2052 KB Output isn't correct
11 Incorrect 1365 ms 4004 KB Output isn't correct
12 Execution timed out 2055 ms 20968 KB Time limit exceeded
13 Incorrect 1693 ms 24828 KB Output isn't correct