oj.uz

답안 #336799

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

		int v1 = queryL(left,b,mid,p,x);
		if(v1 != n + 1) return v1;
		return 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);
		}
		int v1 = queryR(right,mid+1,e,p,x);
		if(v1 != 0) return v1;
		return queryR(left,b,mid,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

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:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |      int mid=b+e>>1;
      |              ~^~
cake.cpp: In member function 'int segtree::query(int, int, int, int, int)':
cake.cpp:71:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |   int mid=b+e>>1;
      |           ~^~
cake.cpp: In function 'int main()':
cake.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |   scanf("%d",&d[i]);
      |   ~~~~~^~~~~~~~~~~~
cake.cpp:106:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |    scanf("%d%d",&x,&e);
      |    ~~~~~^~~~~~~~~~~~~~
cake.cpp:145:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  145 |    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 13 ms 364 KB Output is correct
5 Correct 32 ms 1004 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 752 ms 876 KB Output is correct
2 Correct 457 ms 1004 KB Output is correct
3 Correct 523 ms 1004 KB Output is correct
4 Correct 326 ms 1004 KB Output is correct
5 Correct 825 ms 1900 KB Output is correct
6 Correct 718 ms 2028 KB Output is correct
7 Correct 595 ms 2028 KB Output is correct
8 Correct 371 ms 2028 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 7532 KB Output is correct
2 Correct 345 ms 7404 KB Output is correct
3 Correct 342 ms 7404 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 537 ms 17644 KB Output is correct
6 Correct 544 ms 17772 KB Output is correct
7 Correct 409 ms 17388 KB Output is correct

Subtask #4
33.333333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 620 KB Output is correct
2 Correct 114 ms 748 KB Output is correct
3 Correct 221 ms 3820 KB Output is correct
4 Correct 262 ms 3820 KB Output is correct
5 Correct 385 ms 748 KB Output is correct
6 Correct 434 ms 5100 KB Output is correct
7 Correct 447 ms 1516 KB Output is correct
8 Correct 358 ms 7020 KB Output is correct
9 Execution timed out 2099 ms 18536 KB Time limit exceeded
10 Correct 1320 ms 1604 KB Output is correct
11 Correct 1494 ms 3052 KB Output is correct
12 Execution timed out 2084 ms 15212 KB Time limit exceeded
13 Correct 1691 ms 18668 KB Output is correct