Submission #397627

#	Time	Username	Problem	Language	Result	Execution time	Memory
397627		MrRobot_28	Index (COCI21_index)	C++17	110 / 110	300 ms	9924 KiB

index

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define sz(a) (int)a.size()
const int mod = 1e9 + 7;
const int N = 2e5+ 100;
int cnt[N];
const int T = 500;
bool cmp(pair <pair <int, int>, int> a, pair <pair <int, int>, int> b)
{
    if((a.X.X / T) == (b.X.X / T))
    {
        return a.X.Y < b.X.Y;
    }
    return (a.X.X / T) < (b.X.X / T);
}
int n, q;
int h[N];
signed main()
{
  //  ifstream cin("input1.txt.4c");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i = 0; i < n; i++)
    {
        cin >> h[i];
    }
    vector <pair <pair <int, int>, int> > queries;
    for(int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        queries.push_back({{l, r}, i});
    }
    sort(queries.begin(), queries.end(), cmp);
    int suma, it;
    vector <int> qans(q);
    for(int i = 0; i < sz(queries); i++)
    {
        int l = queries[i].X.X;
        int r = queries[i].X.Y;
        if(i == 0 || (queries[i].X.X / T) != (queries[i - 1].X.X / T))
        {
            fill(cnt, cnt + N, 0);
            suma = 0;
            it = 1;
            for(int j = l; j <= r; j++)
            {
                suma++;
                cnt[h[j]]++;
            }
        }
        else
        {
            for(int j = queries[i - 1].X.Y + 1; j <= r; j++)
            {
                if(h[j] >= it)
                {
                    suma++;
                }
                cnt[h[j]]++;
            }
            for(int j = queries[i].X.X; j < queries[i - 1].X.X; j++)
            {
                if(h[j] >= it)
                {
                    suma++;
                }
                cnt[h[j]]++;
            }
            for(int j = queries[i - 1].X.X; j < queries[i].X.X; j++)
            {
                if(h[j] >= it)
                {
                    suma--;
                }
                cnt[h[j]]--;
            }
        }
        while(suma < it)
        {
            it--;
            suma += cnt[it];
        }
        while(suma - cnt[it] >= it + 1)
        {
            suma -= cnt[it];
            it++;
        }/*
        for(int e = 0; e <= n; e++)
        {
            cout << cnt[e] << " ";
        }
        cout << "\n";
        cout << l << " " << r << " " << suma << " " << it << "\n";*/
        qans[queries[i].Y] = it;
    }
    for(int j =0; j < q; j++)
    {
        cout << qans[j] << "\n";
    }
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50