oj.uz

답안 #679273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679273 2023-01-08T01:29:59 Z gyandevrey6 Election (BOI18_election) C++17
0 / 100
 13 ms 31572 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
//1 => l-1~r 
ll n,q,a[500100];
string s;
 
typedef struct leaf{
	ll minind,maxind;
}leaf;
 
vector<leaf> tree = vector<leaf>(2000100);
 
void init(ll l,ll r,ll ind)
{
	if(l==r)
	{
		tree[ind].minind = tree[ind].maxind = l;
		return;
	}
	init(l,(l+r)/2,ind*2);
	init((l+r)/2+1,r,ind*2+1);
	tree[ind].minind = a[tree[ind*2].minind]>=a[tree[ind*2+1].minind]?tree[ind*2+1].minind:tree[ind*2].minind;
	tree[ind].maxind = a[tree[ind*2].maxind]<=a[tree[ind*2+1].maxind]?tree[ind*2+1].maxind:tree[ind*2].maxind;
}
 
leaf query(ll l,ll r,ll s,ll e,ll ind)
{
	if(s<=l&&r<=e)
		return tree[ind];
	if(e<l||r<s)
	{
		leaf ret;
		ret.minind = ret.maxind = -1;
		return ret;
	}
	leaf r1=query(l,(l+r)/2,s,e,ind*2);
	leaf r2=query((l+r)/2+1,r,s,e,ind*2+1);
	leaf ret;
	if(r1.minind==-1)
		return r2;
	if(r2.minind==-1)
		return r1;
	ret.minind = a[r1.minind]>=a[r2.minind]?r2.minind:r1.minind;
	ret.maxind = a[r1.maxind]<=a[r2.maxind]?r2.maxind:r1.maxind;
	return ret;
}
 
ll ans(ll l,ll r)
{
	leaf t = query(0,n,l,r,1);
	ll b = a[t.maxind]-a[r];
	ll av = a[l]-a[t.minind];
	leaf t2 = query(0,n,l,t.maxind,1);
	leaf t3 = query(0,n,t.minind,r,1);
	ll c = a[l]-a[t2.minind];
	ll d = a[t3.maxind]-a[r];
	
	return c+d+max(b-d,av-c);
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	cin>>s;
	for(ll i=0;i<n;i++)
	{
		if(s[i]=='C')
			a[i+1] = a[i]+1;
		else
			a[i+1] = a[i]-1;
	}
	init(0,n,1);
	cin>>q;
	while(q--)
	{
		ll l,r;
		cin>>l>>r;
		cout<<ans(l-1,r)<<"\n";
	}
}

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 31572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 31572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 31572 KB Output isn't correct
2 Halted 0 ms 0 KB -