oj.uz

답안 #336797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
336797 2020-12-16T20:41:54 Z nafis_shifat 케이크 (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 25068 KB 
#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;
			cin>>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

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: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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 14 ms 492 KB Output is correct
5 Correct 35 ms 1132 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 885 ms 5372 KB Output is correct
2 Correct 591 ms 5484 KB Output is correct
3 Correct 646 ms 5612 KB Output is correct
4 Correct 448 ms 5484 KB Output is correct
5 Correct 958 ms 6636 KB Output is correct
6 Correct 865 ms 7020 KB Output is correct
7 Correct 720 ms 6892 KB Output is correct
8 Correct 504 ms 7020 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 383 ms 9064 KB Output is correct
2 Correct 345 ms 8940 KB Output is correct
3 Correct 343 ms 8940 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 549 ms 20076 KB Output is correct
6 Correct 539 ms 20076 KB Output is correct
7 Correct 451 ms 20076 KB Output is correct

Subtask #4
33.333333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 1004 KB Output is correct
2 Correct 125 ms 1132 KB Output is correct
3 Correct 230 ms 4972 KB Output is correct
4 Correct 274 ms 4844 KB Output is correct
5 Correct 416 ms 1900 KB Output is correct
6 Correct 462 ms 7020 KB Output is correct
7 Correct 482 ms 3180 KB Output is correct
8 Correct 417 ms 9732 KB Output is correct
9 Execution timed out 2065 ms 24408 KB Time limit exceeded
10 Correct 1397 ms 5324 KB Output is correct
11 Correct 1585 ms 7404 KB Output is correct
12 Execution timed out 2095 ms 21228 KB Time limit exceeded
13 Correct 1821 ms 25068 KB Output is correct