oj.uz

답안 #336798

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 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 33 ms 1004 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 747 ms 876 KB Output is correct
2 Correct 466 ms 1004 KB Output is correct
3 Correct 524 ms 1004 KB Output is correct
4 Correct 324 ms 1004 KB Output is correct
5 Correct 814 ms 1900 KB Output is correct
6 Correct 717 ms 2156 KB Output is correct
7 Correct 570 ms 2028 KB Output is correct
8 Correct 361 ms 2028 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 378 ms 7532 KB Output is correct
2 Correct 356 ms 7404 KB Output is correct
3 Correct 341 ms 7532 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 555 ms 17696 KB Output is correct
6 Correct 547 ms 17644 KB Output is correct
7 Correct 454 ms 17444 KB Output is correct

Subtask #4
33.333333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 644 KB Output is correct
2 Correct 115 ms 748 KB Output is correct
3 Correct 219 ms 3820 KB Output is correct
4 Correct 259 ms 3820 KB Output is correct
5 Correct 389 ms 748 KB Output is correct
6 Correct 436 ms 5228 KB Output is correct
7 Correct 458 ms 1516 KB Output is correct
8 Correct 359 ms 7020 KB Output is correct
9 Execution timed out 2073 ms 19180 KB Time limit exceeded
10 Correct 1298 ms 1704 KB Output is correct
11 Correct 1516 ms 3308 KB Output is correct
12 Execution timed out 2088 ms 15280 KB Time limit exceeded
13 Correct 1702 ms 18728 KB Output is correct