Submission #336798

#	Time	Username	Problem	Language	Result	Execution time	Memory
336798		nafis_shifat	Cake (CEOI14_cake)	C++14	83.33 / 100	2088 ms	19180 KiB

cake

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=2e5+5e4+7;
const int inf=1e9;
struct segtree {
	int tree[4*mxn];
	int n;
	void init(int N) {
		n = N;
		for(int i = 1; i <= 4 * n; i++) tree[i] = inf;	
	}

    void update(int node,int b,int e,int p,int v) {
    	if(b > p || e < p) return;
    	if(b == e) {
    		tree[node] = v;
    		return;
    	}
    	int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;
		update(left,b,mid,p,v);
		update(right,mid+1,e,p,v);
		tree[node] = max(tree[left],tree[right]);
    }
    int queryL(int node,int b,int e,int p,int x) {
    	if(e < p) return n + 1;
    	if(tree[node] < x) return n + 1;
    	if(b == e) {
    		return b;
    	}
    	int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;
		if(b >= p) {
			if(tree[left] >= x) return queryL(left,b,mid,p,x);
			else return queryL(right,mid+1,e,p,x);
		}
		return min(queryL(left,b,mid,p,x),queryL(right,mid+1,e,p,x));
    }

    int queryR(int node,int b,int e,int p,int x) {
    	if(b > p) return 0;
    	if(tree[node] < x) return 0;
    	if(b == e) {
    		return b;
    	}
    	int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;
		if(e <= p) {
			if(tree[right] >= x) return queryR(right,mid+1,e,p,x);
			else return queryR(left,b,mid,p,x);
		}
		return max(queryR(left,b,mid,p,x),queryR(right,mid+1,e,p,x));
    }

    
	int query(int node,int b,int e,int l,int r) {
		if(e < l || b > r) return 0;
		if(b >= l && e <= r) {
			return tree[node];
		}
		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;
		return max(query(left,b,mid,l,r),query(right,mid+1,e,l,r));
	}
} seg;
int main() {
	int n,a;
	cin>>n>>a;

	int d[n+1];
	set<pii> st;
	for(int i = 1; i <= n; i++) {
		scanf("%d",&d[i]);
		st.insert({d[i],i});
	}	

	seg.init(n);

	for(int i = 1; i <= n; i++) seg.update(1,1,n,i,d[i]);




	int q;
	cin>>q;

	
	while(q--) {
		
		char c;
		cin>>c;

		if(c == 'E') {
			int x,e;
			scanf("%d%d",&x,&e);

			int v = 1;

			auto it = st.rbegin();
			stack<pii> s;

			for(; v < e; it++, v++) {
				s.push(*it);
			}
			int f = -1;
			if(!s.empty()) {
				f = s.top().first;
			}


			while(!s.empty()) {
				pii t = s.top();
				s.pop();

				st.erase(t);
				st.insert({t.first + 1,t.second});
				d[t.second] = t.first + 1;
				seg.update(1,1,n,t.second,d[t.second]);
			}


			if(f == -1) {
				f = it->first + 1;
			} 


			st.erase({d[x],x});
			st.insert({f,x});
			d[x] = f;
			seg.update(1,1,n,x,d[x]);

		} else {
			int x;
			scanf("%d",&x);
			if(x == a) {
				printf("0\n");
				continue;
			}

			if(x < a) {
				int v = seg.query(1,1,n,x,a-1);
				int ind = seg.queryL(1,1,n,a+1,v);
				int res = ind - 1 - a + a - x;
				printf("%d\n",res);

			} else {
				int v = seg.query(1,1,n,a+1,x);


				int ind = seg.queryR(1,1,n,a-1,v);
				int res = a - ind - 1 + x - a;
				printf("%d\n",res);
			}
		}

	}




}

Compilation message (stderr)

cake.cpp: In member function 'void segtree::update(int, int, int, int, int)':
cake.cpp:21:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |      int mid=b+e>>1;
      |              ~^~
cake.cpp: In member function 'int segtree::queryL(int, int, int, int, int)':
cake.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |      int mid=b+e>>1;
      |              ~^~
cake.cpp: In member function 'int segtree::queryR(int, int, int, int, int)':
cake.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |      int mid=b+e>>1;
      |              ~^~
cake.cpp: In member function 'int segtree::query(int, int, int, int, int)':
cake.cpp:66:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |   int mid=b+e>>1;
      |           ~^~
cake.cpp: In function 'int main()':
cake.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |   scanf("%d",&d[i]);
      |   ~~~~~^~~~~~~~~~~~
cake.cpp:101:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |    scanf("%d%d",&x,&e);
      |    ~~~~~^~~~~~~~~~~~~~
cake.cpp:140:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  140 |    scanf("%d",&x);
      |    ~~~~~^~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 33.333333 / 50