QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#346069#7949. K-Lotterytuanlinh123Compile Error//C++202.6kb2024-03-07 20:08:322024-03-07 20:08:35

Judging History

你现在查看的是最新测评结果

  • [2024-03-07 20:08:35]
  • 评测
  • [2024-03-07 20:08:32]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const __int128_t base=41597, Mod=100000004987;
__int128_t po[1000005];
ll a[1000005];
map <__int128_t, ll> trace;
vector <ll> tick[1005];

namespace SegTree
{
    struct Node
    {
        ll cnt=0;
        __int128_t val=0;
        Node(){}
        Node(ll x): cnt(!!x), val(x){}
        inline Node operator + (const Node &a) const
        {
            Node ans;
            ans.cnt=cnt+a.cnt;
            ans.val=(val+a.val*po[cnt])%Mod;
            return ans;
        }
    };

    ll n;
    Node St[4000005];
    void init(ll sz) {n=sz;}

    inline void update(ll i, ll Start, ll End, ll idx, ll val)
    {
        if (Start>idx || End<idx) return;
        if (Start==End) {St[i]=Node(val); return;}
        ll mid=(Start+End)/2;
        if (idx<=mid) update(i*2, Start, mid, idx, val);
        if (mid+1<=idx) update(i*2+1, mid+1, End, idx, val); 
        St[i]=St[i*2]+St[i*2+1];
    }

    inline void update(ll idx, ll val) {update(1, 1, n, idx, val);}
    inline __int128_t query() {return St[1].val;}
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll k, m, n; cin >> k >> m >> n;
    __int128_t sum=0; 
    for (ll i=0; i<=n; i++)
    {
        po[i]=i?po[i-1]*base%Mod:1;
        if (i<k) sum=(sum+po[i])%Mod;
    }
    for (ll i=1; i<=m; i++)
    {
        tick[i].resize(k);
        vector <pll> num;
        for (ll j=0; j<k; j++)
            cin >> tick[i][j], num.pb({tick[i][j], j+1});
        sort(num.begin(), num.end());
        __int128_t val=0;
        for (ll j=0; j<k; j++)
            val=(val+po[j]*num[j].se)%Mod;
        trace[val]=i;
    }
    vector <ll> num;
    for (ll i=1; i<=n; i++) cin >> a[i], num.pb(a[i]);
    sort(num.begin(), num.end());
    num.resize(unique(num.begin(), num.end())-num.begin());
    SegTree::init(n);
    for (ll i=1; i<=n; i++)
    {
        a[i]=lower_bound(num.begin(), num.end(), a[i])-num.begin()+1;
        SegTree::update(a[i], i);
        if (i>=k)
        {
            __int128_t val=(SegTree::query()-sum*(i-k)%Mod+Mod)%Mod;
            if (trace[val])
            {
                ll id=trace[val];
                for (ll j:tick[id]) cout << j << " ";
                exit(0);
            }
            SegTree::update(a[i-k+1], 0);
        }   
    }
    cout << 0;
}


Details

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Rb_tree<__int128, std::pair<const __int128, long long int>, std::_Select1st<std::pair<const __int128, long long int> >, std::less<__int128>, std::allocator<std::pair<const __int128, long long int> > >::_Rb_tree_impl<std::less<__int128>, true>::~_Rb_tree_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::_Rb_tree_node<std::pair<const __int128, long long int> >]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/map:62,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:152:
/usr/include/c++/13/bits/stl_tree.h:662:16: note: called from here
  662 |         struct _Rb_tree_impl
      |                ^~~~~~~~~~~~~