/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 1700ms 4.598 MiB
#4 Accepted 1ms 532.0 KiB
#5 Accepted 1ms 488.0 KiB
#6 Accepted 2042ms 4.598 MiB
#7 Accepted 75ms 4.52 MiB
#8 Accepted 79ms 4.77 MiB
#9 Time Exceeded ≥2600ms ≥6.297 MiB
#10 Time Exceeded ≥2600ms ≥5.547 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 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(200010);
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;
   }
};
map<ll,ll>coun;
ll mp[300010];
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()
{
    ll n,q;
    scanf("%d%d",&n,&q);
    ll arr[n+1];
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
    query qu[q];
    for(int j=0;j<q;j++)
    {
        scanf("%d%d",&qu[j].l,&qu[j].r);
       //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 out=INT_MAX;
        for(int i=x.size()-1;i>=0;i--)
        {
            pair<ll,ll>p=*x.find_by_order(i);
            if(p.first>(r-l+1)/3)
            {
                out=min(out,p.second);
            }
            else
            {
                break;
            }
        }
        if(out==INT_MAX)ans[j]=-1;
        else ans[j]=out;
    }
    for(int i=0;i<q;i++)printf("%d\n",ans[i]);
}

Information

Submit By
Type
Submission
Problem
P1103 The Secret Garden of Numbers
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-06 15:56:32
Judged At
2024-11-06 15:56:32
Judged By
Score
40
Total Time
≥2600ms
Peak Memory
≥6.297 MiB