oj.uz

답안 #30820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30820 2017-07-27T05:37:34 Z zscoder 케이크 (CEOI14_cake) C++14
100 / 100
 1523 ms 28988 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef tree<ll,null_type,greater<ll>,rb_tree_tag,tree_order_statistics_node_update> pbds;

int a[250001];
int query[511111];
int tmpidx[511111];
int st[1000001];
bool used[250001];
vector<pair<char,pair<int,int> > > queries;

void build(int id, int l, int r)
{
	if(r-l<2)
	{
		st[id]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(id*2,l,mid);
	build(id*2+1,mid,r);
	st[id]=max(st[id*2],st[id*2+1]);
}

void update(int id, int l, int r, int pos, int v)
{
	if(pos>=r||pos<l) return ;
	if(r-l<2)
	{
		st[id]=v;
		return ;
	}
	int mid=(l+r)>>1;
	update(id*2,l,mid,pos,v);
	update(id*2+1,mid,r,pos,v);
	st[id]=max(st[id*2],st[id*2+1]);
}

int querymax(int id, int l, int r, int ql, int qr)
{
	if(ql>=r||l>=qr) return -1;
	//cerr<<id<<' '<<l<<' '<<r<<' '<<ql<<' '<<qr<<' '<<st[id]<<'\n';
	if(ql<=l&&r<=qr) return st[id];
	int mid=(l+r)>>1;
	return max(querymax(id*2,l,mid,ql,qr),querymax(id*2+1,mid,r,ql,qr));
}

int queryr(int id, int l, int r, int ql, int qr, int v)
{
	if(ql>=r||l>=qr) return -1;
	if(r-l<2)
	{
		//cerr<<id<<' '<<l<<' '<<r<<' '<<ql<<' '<<qr<<' '<<v<<' '<<st[id]<<'\n';
		if(st[id]>=v) return l;
		else return -1;
	}
	int mid=(l+r)>>1;
	if(ql<=l&&r<=qr)
	{
		//cerr<<id<<' '<<l<<' '<<r<<' '<<ql<<' '<<qr<<' '<<v<<' '<<st[id*2+1]<<'\n';
		if(st[id*2+1]>=v)
		{
			return queryr(id*2+1,mid,r,ql,qr,v);
		}
		else
		{
			return queryr(id*2,l,mid,ql,qr,v);
		}
	}
	return max(queryr(id*2,l,mid,ql,qr,v),queryr(id*2+1,mid,r,ql,qr,v));
}	

int queryl(int id, int l, int r, int ql, int qr, int v)
{
	if(ql>=r||l>=qr) return 100000000;
	if(r-l<2)
	{
		if(st[id]>=v) return l;
		else return 100000000;
	}
	int mid=(l+r)>>1;
	if(ql<=l&&r<=qr)
	{
		if(st[id*2]>=v)
		{
			return queryl(id*2,l,mid,ql,qr,v);
		}
		else
		{
			return queryl(id*2+1,mid,r,ql,qr,v);
		}
	}
	return min(queryl(id*2,l,mid,ql,qr,v),queryl(id*2+1,mid,r,ql,qr,v));
}

int main()
{
	//ios_base::sync_with_stdio(0); cin.tie(0);
	int n,s;
	scanf("%d %d",&n,&s);
	s--;
	for(int i=0;i<n;i++)
	{
		scanf("%d",a+i);
		a[i]--;
	}
	int q; scanf("%d",&q);
	int upd=0;
	for(int i=0;i<q;i++)
	{
		char c; int pos;
		scanf(" %c %d",&c,&pos);
		pos--;
		if(c=='E')
		{
			int v; scanf("%d",&v);
			v--;
			tmpidx[i]=v;
			queries.pb(mp(c,mp(pos,v)));
		}
		else
		{
			queries.pb(mp(c,mp(pos,-1)));
		}
	}
	build(1,0,n);
	set<pair<int,int> > cur;
	for(int i=0;i<n;i++) cur.insert(mp(-a[i],i));
	for(int i = 0; i < q; i++)
	{
		char c = queries[i].fi;
		int pos = queries[i].se.fi;
		int v = queries[i].se.se;
		if(c=='E')
		{
			cur.erase(mp(-a[pos],pos));
			vector<ii> hold;
			int num = n + upd;
			for(int i = 0; i < v; i++)
			{
				ii tmp = (*cur.begin());
				cur.erase(cur.begin());
				tmp.fi=-num;
				a[tmp.se]=num;
				update(1,0,n,tmp.se,num);
				hold.pb(tmp);
				num--;
			}
			update(1,0,n,pos,num);
			a[pos]=num;
			hold.pb(mp(-num,pos));
			for(int i=0;i<hold.size();i++) cur.insert(hold[i]);
			upd++;
		}
		else
		{
			if(s==pos)
			{
				printf("0\n");
			}
			else if(s>pos)
			{
				int tmp = querymax(1,0,n,pos,s);
				int ridx = queryl(1,0,n,s+1,n,tmp);
				if(ridx>n) ridx=n;
				ridx--;
				printf("%d\n",ridx-pos);
			}
			else
			{
				int tmp = querymax(1,0,n,s+1,pos+1);
				int lidx = queryr(1,0,n,0,s,tmp);
				printf("%d\n",pos-1-lidx);
			}
		}		
	}
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:165:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<hold.size();i++) cur.insert(hold[i]);
                 ^
cake.cpp:113:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&s);
                      ^
cake.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",a+i);
                  ^
cake.cpp:120:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int q; scanf("%d",&q);
                       ^
cake.cpp:125:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d",&c,&pos);
                          ^
cake.cpp:129:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int v; scanf("%d",&v);
                         ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 11148 KB Output is correct
2 Correct 0 ms 11148 KB Output is correct
3 Correct 0 ms 11148 KB Output is correct
4 Correct 6 ms 11320 KB Output is correct
5 Correct 26 ms 11816 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 769 ms 20448 KB Output is correct
2 Correct 489 ms 20448 KB Output is correct
3 Correct 579 ms 20448 KB Output is correct
4 Correct 389 ms 20448 KB Output is correct
5 Correct 746 ms 20448 KB Output is correct
6 Correct 746 ms 20448 KB Output is correct
7 Correct 553 ms 20448 KB Output is correct
8 Correct 346 ms 20448 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 223 ms 17384 KB Output is correct
2 Correct 126 ms 17384 KB Output is correct
3 Correct 119 ms 17384 KB Output is correct
4 Correct 0 ms 11148 KB Output is correct
5 Correct 409 ms 24380 KB Output is correct
6 Correct 399 ms 24380 KB Output is correct
7 Correct 236 ms 24380 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 12384 KB Output is correct
2 Correct 63 ms 12384 KB Output is correct
3 Correct 149 ms 15008 KB Output is correct
4 Correct 209 ms 15008 KB Output is correct
5 Correct 226 ms 15840 KB Output is correct
6 Correct 333 ms 17336 KB Output is correct
7 Correct 296 ms 15840 KB Output is correct
8 Correct 436 ms 18920 KB Output is correct
9 Correct 1353 ms 28988 KB Output is correct
10 Correct 859 ms 20448 KB Output is correct
11 Correct 1143 ms 20448 KB Output is correct
12 Correct 1523 ms 26744 KB Output is correct
13 Correct 1229 ms 28988 KB Output is correct