/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 540.0 KiB
#2 Accepted 2ms 552.0 KiB
#3 Accepted 1862ms 8.461 MiB
#4 Accepted 1ms 540.0 KiB
#5 Accepted 2ms 452.0 KiB
#6 Wrong Answer 2431ms 8.445 MiB
#7 Accepted 98ms 8.418 MiB
#8 Wrong Answer 103ms 8.582 MiB

Code

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define endl '\n'
#define all(v) v.begin(), v.end()
#define pb push_back //
#define fi first                         //
#define se second                        //
#define yes cout << "YES" << endl        //
#define no cout << "NO" << endl          //
#define M 1000000007                     // 1e9+7
#define gcd(a, b) __gcd(a, b)            //
#define lcm(a, b) a *b / gcd(a, b)       //
#define memz(a) memset(a, 0, sizeof(a))  //
#define memn(a) memset(a, -1, sizeof(a)) //
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key

ll block=sqrt(300010);
struct query
{
   ll l,r,i;
   bool operator <(query b)
   {
    if(this->l/block!=b.l/block)return this->l/block<b.l/block;
    else return this->r<b.r;
   }
};
ll mp[200010];
pbds x;
ll l,r;
void add(ll val)
{
    if(mp[val])x.erase(x.find({mp[val],val}));
    mp[val]++;
    x.insert({mp[val],val});
}
void remove(ll val)
{
    if(mp[val])x.erase(x.find({mp[val],val}));
    mp[val]--;
    if(mp[val])x.insert({mp[val],val});
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,q;
    cin>>n>>q;
    ll arr[n+1];
    for(int i=1;i<=n;i++)cin>>arr[i];
    query qu[q];
    for(int j=0;j<q;j++)
    {
       cin>>qu[j].l>>qu[j].r;
       qu[j].i=j;
    }
    sort(qu,qu+q);
    ll ans[q];
    ll l=1,r=0;
    for(int i=0;i<q;i++)
    {
        ll s=qu[i].l;
        ll e=qu[i].r;
        ll j=qu[i].i;
        while(e>r)
        {
            r++;
            add(arr[r]);
        }
        while(s<l)
        {
            l--;
            add(arr[l]);
        }
        while(e<r)
        {
           
            remove(arr[r]);
            r--;
        }
        while(s>l)
        {
            remove(arr[l]);
            l++;
        }
        ll a=0,b=x.size()-1;
        ll out=-1;
        while(a<=b)
        {
            ll m=(a+b)/2;
            pair<ll,ll>p=*x.find_by_order(m);
            if(p.first>((e-s+1)/3))
            {
                out=p.second;
                b=m-1;
            }
            else
            {
                a=m+1;
            }
        }
        ans[j]=out;
    }
    for(int i=0;i<q;i++)cout<<ans[i]<<endl;
}

Information

Submit By
Type
Submission
Problem
P1103 The Secret Garden of Numbers
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-06 13:58:41
Judged At
2024-11-06 13:58:41
Judged By
Score
30
Total Time
2431ms
Peak Memory
8.582 MiB