제출 #315776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
315776		i_am_noob	Election (BOI18_election)	C++17	100 / 100	801 ms	40288 KiB

election

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
//#define inf 2000000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=500005;
//i_am_noob
int n,a[maxn],q,l,r;
string str;

struct noob{
    int minn,maxx,diffmax;
    noob(){}
    noob(int i, int j, int k):minn(i),maxx(j),diffmax(k){}
};
noob val[maxn*4],def(inf,-inf,-inf);

noob Merge(noob i, noob j){return noob(min(i.minn,j.minn),max(i.maxx,j.maxx),max(max(i.diffmax,j.diffmax),j.maxx-i.minn));}

void build(int k, int l, int r){
    if(l==r){
        val[k]=noob(a[l-1],a[l-1],0);
        return;
    }
    build(k<<1,l,l+r>>1),build(k<<1|1,(l+r>>1)+1,r);
    val[k]=Merge(val[k<<1],val[k<<1|1]);
}

noob query(int k, int l, int r, int ql, int qr){
    if(l>qr||r<ql) return def;
    if(ql<=l&&qr>=r) return val[k];
    return Merge(query(k<<1,l,l+r>>1,ql,qr),query(k<<1|1,(l+r>>1)+1,r,ql,qr));
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n >> str;
    a[0]=0;
    rep(n) a[i+1]=a[i]+(str[i]=='C'?1:-1);
    build(1,1,n+1);
    cin >> q;
    while(q--){
        cin >> l >> r;
        noob x=query(1,1,n+1,l,r+1);
        print1(a[l-1]-x.minn+x.diffmax-(a[r]-x.minn));
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

election.cpp: In function 'void build(long long int, long long int, long long int)':
election.cpp:53:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     build(k<<1,l,l+r>>1),build(k<<1|1,(l+r>>1)+1,r);
      |                  ~^~
election.cpp:53:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     build(k<<1,l,l+r>>1),build(k<<1|1,(l+r>>1)+1,r);
      |                                        ~^~
election.cpp: In function 'noob query(long long int, long long int, long long int, long long int, long long int)':
election.cpp:60:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     return Merge(query(k<<1,l,l+r>>1,ql,qr),query(k<<1|1,(l+r>>1)+1,r,ql,qr));
      |                               ~^~
election.cpp:60:60: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     return Merge(query(k<<1,l,l+r>>1,ql,qr),query(k<<1|1,(l+r>>1)+1,r,ql,qr));
      |                                                           ~^~

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18