Submission #1131676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131676		Icelast	Bali Sculptures (APIO15_sculpture)	C++17	0 / 100	390 ms	327680 KiB

sculpture

#include <iostream>
#include <bits/stdc++.h>
#define ll int
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9, mod = 998244353;
struct Data{
    int mx = INF, cnt = 0;
};
Data chmax(Data a, Data b){
    if(a.mx < b.mx){
        return a;
    }else if(a.mx > b.mx){
        return b;
    }else{
        return {a.mx, (a.cnt+b.cnt)%mod};
    }
}
struct Info{
    vector<vector<Data>> f;
    Info() : f(64, vector<Data>(2, Data())){f[0][0] = {0, 1};}
};
Info insert(Info a, int b){
    Info res;
    for(int j = 0; j < 64; j++){
        res.f[j][0] = a.f[j][0];
        Data either2 = chmax(a.f[j^b][0], a.f[j^b][1]);
        res.f[j][1] = chmax(a.f[j][1], {either2.mx+1, either2.cnt});
    }
    return res;
}
Info merge(Info a, Info b){
    Info res;
    for(int i = 0; i < 64; i++){
        for(int t1 = 0; t1 <= 1; t1++){
            for(int t2 = 0; t2 <= 1; t2++){
                if((t1|t2) == 0) continue;
                res.f[0][1] = chmax(res.f[0][1], {a.f[i][t1].mx+b.f[i][t2].mx, a.f[i][t1].cnt*b.f[i][t2].cnt%mod});
            }
        }
    }
    return res;
}
struct MeowTree{
    struct Node{
        vector<Info> lt, rt;
        int mid;
    };
    int n, N;
    vector<Node> T;
    MeowTree(int n, vector<int> a) : n(n){
        N = 1;
        while(N < n){
            N*=2;
        }
        T.resize(N*2);
        for(int i = n+1; i <= N; i++){
            a.push_back(0);
        }
        auto build = [&](auto build, int node, int low, int high) -> void{
            int mid = (low+high)/2;
            T[node].mid = mid;
            if(low == high){
                T[node].lt.push_back(insert(Info(), a[mid]));
                return;
            }
            T[node].lt.push_back(insert(Info(), a[mid]));
            T[node].rt.push_back(insert(Info(), a[mid+1]));
            for(int i = mid-1; i >= low; i--){
                if(i >= n) continue;
                T[node].lt.push_back(insert(T[node].lt.back(), a[i]));
            }
            for(int i = mid+2; i <= min(n, high); i++){
                T[node].rt.push_back(insert(T[node].rt.back(), a[i]));
            }
            build(build, node*2, low, mid);
            build(build, node*2+1, mid+1, high);
        };
        build(build, 1, 1, N);
    }
    Info query(int l, int r){
        if(l == r) return T[l+N-1].lt[0];
        int low = l+N-1, high = r+N-1;
        while(low != high){
            if(low > high) swap(low, high);
            high/=2;
        }
        int node = low, mid = T[node].mid;
        return merge(T[node].lt[mid-l], T[node].rt[r-mid-1]);
    }
};
void solve(){
    int n, q;
    n = 1e5; q = 0;
    vector<int> a(n+1);
    for(int i = 1; i <= n; i++){
        a[i] = 7;
    }
    vector<int> pf(n+1, 0);
    for(int i = 1; i <= n; i++){
        pf[i] = pf[i-1]^a[i];
    }
    MeowTree T(n, a);
    for(int i = 1; i <= q; i++){
        int l, r;
        l = 1, r = n;
        Info res = T.query(l, r);
        if(res.f[0][1].mx == INF){
            cout << -1 << "\n";
            continue;
        }
        cout << r-l+1-res.f[0][1].mx << " " << res.f[0][1].cnt << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

sculpture.cpp:5:36: warning: overflow in conversion from 'double' to 'int' changes value from '4.0e+18' to '2147483647' [-Woverflow]
    5 | const ll maxn = 2*1e5+5, INF = 4e18+9, mod = 998244353;
      |                                ~~~~^~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29