oj.uz

답안 #611468

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
611468 2022-07-29T05:12:23 Z temporary_juggernaut Election (BOI18_election) C++14
0 / 100
 4 ms 596 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int n,q;
int pref[500005];
int mn[500005][20];
int suff[500005];
int mn2[500005][20];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	string s;
	cin>>s;
	for(int i=1;i<=n;i++){
		pref[i]=pref[i-1];
		if(s[i-1]=='C')pref[i]++;
		else pref[i]--;
		mn[i][0]=pref[i];
	}
	for(int i=n;i;i--){
		suff[i]=suff[i+1];
		if(s[i-1]=='C')suff[i]++;
		else suff[i]--;
		mn2[i][0]=suff[i];
	}
	for(int j=1;j<20;j++)
	for(int i=1;i+(1<<j)-1<=n;i++){
		mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
		mn2[i][j]=min(mn2[i][j-1],mn2[i+(1<<(j-1))][j-1]);
	}
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		int len=__lg(r-l+1);
		int m=min(min(mn[l][len],mn[r-(1<<len)+1][len])-pref[l-1],min(mn2[l][len],mn2[r-(1<<len)+1][len])-suff[r+1]);
		umin(m,0);
		cout<<-m<<endl;
	}
}

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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