제출 #844382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
844382		vjudge1	Nivelle (COCI20_nivelle)	C++17	24 / 110	1046 ms	16220 KiB

nivelle

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define bg begin
#define vi vector<int>
#define vvi vector<vi> 
#define vp vector<pii>
#define ppi pair<pii,int>
#define endl '\n'
#define triple tuple<int,int,int>
#define ppp pair<pii,pii>
#define pip pair<int,pii>
#define vpp vector<ppi>
#define sp << " " << 
#define ff first
#define ss second
#define F(xxx,n) for (int xxx=1;xxx<=n;++xxx)
#define FF(xxx,sss,yyy) for (int xxx=sss;xxx<=yyy;++xxx)
#define pb push_back
const int MOD = 1e9+7;
const int inf = 2e18;

struct Node{
    int mask,len,L,R;
    double value;
    Node(int msk = 0,int l = 0,double v = 1.0,int left=0,int right=0) {
        mask = msk;
        value = v;
        len = l;
        L = left;
        R = right;
    };
};

Node merge(Node a,Node b){
    int msk = a.mask|b.mask;
    int pc = __builtin_popcount(msk);
    int ln = a.len+b.len;
    return Node(msk,ln,((double)pc)/(ln),a.L,b.R);
}

const int N = 1e5;
string s;
vector<Node> tree(4*N);


double best = 1;
pii ans = {1,1};
void build(int node,int l,int r) {
    if (l == r) {
        //cout << l sp (1<<(s[l-1]-'a')) << endl;
        tree[node] = Node((1<<(s[l-1]-'a')),1,1,1,1);
        return;
    }
    int m = (l+r) >> 1;
    build(2*node,l,m);
    build(2*node+1,m+1,r);
    tree[node] = merge(tree[2*node],tree[2*node+1]);
}

Node query(int node,int l,int r,int L,int R) {
    if (l > R || r < L) return Node(0,0,1,0,0);
    if (l >= L && r <= R) return tree[node];
    int m = (l+r) >> 1;
    return merge(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
}

void solve() {
    int n;
    cin >> n;
    cin >> s;
    build(1,1,n);
    F(i,n) {
        FF(j,i,n) {
            double x = query(1,1,n,i,j).value;
            if (x < best) {
                ans = {i,j};
                best = x;
            }
        }
    }
    cout << ans.ff sp ans.ss << endl;
}  
 
 

signed main() { 
    #ifdef Local
        freopen("input.in","r",stdin);
        freopen("input.out","w",stdout);
    #endif
    ios_base::sync_with_stdio(0);cin.tie(0);    
    int t = 1;
    //cin >> t;
    while (t--) solve();
}

• Subtask 1: 7 / 7
• Subtask 2: 17 / 17
• Subtask 3: 0 / 13
• Subtask 4: 0 / 25
• Subtask 5: 0 / 48