Submission #1292431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292431		jakekim0105	Election (BOI18_election)	C++17	0 / 100	1 ms	332 KiB

election

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int readChar();
template<class T = int> inline T readInt();
template<class T> inline void writeInt(T x, char end = 0);
inline void writeChar(int x);
inline void writeWord(const char *s);
static const int buf_size = 1 << 18;
inline int getChar(){
    #ifndef LOCAL
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if(pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
    if(pos == len) return -1;
    return buf[pos++];
    #endif
}
inline int readChar(){
    #ifndef LOCAL
    int c = getChar();
    while(c <= 32) c = getChar();
    return c;
    #else
    char c; cin >> c; return c;
    #endif
}
template <class T>
inline T readInt(){
    #ifndef LOCAL
    int s = 1, c = readChar();
    T x = 0;
    if(c == '-') s = -1, c = getChar();
    while('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
    #else
    T x; cin >> x; return x;
    #endif
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x){
    if(write_pos == buf_size) fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt(T x, char end){
    if(x < 0) writeChar('-'), x = -x;
    char s[24]; int n = 0;
    while(x || !n) s[n++] = '0' + x % 10, x /= 10;
    while(n--) writeChar(s[n]);
    if(end) writeChar(end);
}
inline void writeWord(const char *s){
    while(*s) writeChar(*s++);
}
struct Flusher{
    ~Flusher(){ if(write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0; }
}flusher;

#define MAX 1048576
int S[MAX], L[MAX], R[MAX], sz;

void merge(int& xs, int& xl, int& xr, int ls, int ll, int lr, int rs, int rl, int rr){
    xs = rs + ls;
    xl = max(ll, ls + rl);
    xr = max(rr, rs + lr);
}

void pull(int x){
    int l = x << 1, r = x << 1 | 1;
    merge(S[x], L[x], R[x], S[l], L[l], R[l], S[r], L[r], R[r]);
}

int qry(int l, int r){
    l += sz;
    r += sz;
    int ls = 0, ll = 0, lr = 0, rs = 0, rl = 0, rr = 0;
    while(l <= r){
        if(l&1){
            merge(ls, ll, lr, ls, ll, lr, S[l], L[l], R[l]);
            l++;
        }
        if(~r&1){
            merge(rs, rl, rr, S[r], L[r], R[r], rs, rl, rr);
            r--;
        }
        l >>= 1;
        r >>= 1;
    }
    int s;
    merge(s, l, r, ls, ll, lr, rs, rl, rr);
    return max(l, r);
}

int main(){
    int n = readInt();
    sz = 1;
    while(sz <= n)sz <<= 1;
    for(int i = 1; i <= n; i++){
        if(getChar() == 'C'){
            S[i+sz] = L[i+sz] = R[i+sz] = -1;
        }
        else{
            S[i+sz] = L[i+sz] = R[i+sz] = 1;
        }
    }
    for(int i = sz - 1; i; i--)pull(i);
    int q = readInt();
    while(q--){
        int l = readInt(), r = readInt();
        writeInt(qry(l, r), '\n');
    }
}

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