Submission #891938

#	Time	Username	Problem	Language	Result	Execution time	Memory
891938		bibocat	Index (COCI21_index)	C++14	110 / 110	989 ms	64480 KiB

index

#include<iostream>
#include<fstream>
#include<stdio.h>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<deque>
#include<math.h>
#include<ctime>

using namespace std;

#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define long long long
#define mp(a,b) make_pair(a,b)
#define FI first
#define SE second


#define N 200002

const long mod = 998244353;
    
long bit[N];
long a[N];
long n,q;
long res[N];
vector<long> pos[N];
void init()
{
    for(long i = 1;i <= n;++i)
        bit[i] = 0;
}

struct Query{
    long u,v,l,r;
} query[N];


void update(long p,long val)
{
    for(p;p <= n;p += p&-p)
        bit[p] += val;
}

long get(long p)
{
    long res = 0;
    for(p;p > 0;p -= p&-p)
        res += bit[p];
    return res;
}

vector<long> cur[N];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> n >> q;
    for(long i = 1;i <= n;i++)
    {
        cin >> a[i];
        pos[min(a[i],n)].push_back(i);
    }

    for(long i = 1;i <= q;i++)
    {
        res[i] = 1;
        cin >>query[i].u >> query[i].v;
        query[i].l = 1;
        query[i].r = n;
    }

    for(long num = 1;num <= 30;num++)
    {
        for(long i = 1;i <= n;i++)
            cur[i].clear();
        for(long i = 1;i <= q;i++)
            if(query[i].l <= query[i].r)
                cur[(query[i].l+query[i].r)/2].push_back(i);
        init();
        for(long i = n;i >= 1;i--)
        {
            for(long j:pos[i])
            {
                update(j,1);
             //   cout << j << " ";
            }
            for(long j:cur[i])
            {
                long l = query[j].u;
                long r = query[j].v;
                long mid = (query[j].l+query[j].r)/2;
                if(get(r) - get(l-1) >= i)
                {
                    res[j] = i;
                   // cout << get(r) - get(l-1) << " " << l << " " <<r << " " <<endl;
                    query[j].l = mid + 1;
                    //cout << j <<" "<<i<<endl;
                }
                else
                    query[j].r = mid - 1;
            }
        }
     //   cout << endl;
    }
    for(long i = 1;i <= q;i++)
        cout << res[i] <<endl;
    cerr<<"Times:  "<<TIME<<endl;
}

Compilation message (stderr)

index.cpp: In function 'void update(long long int, long long int)':
index.cpp:45:9: warning: statement has no effect [-Wunused-value]
   45 |     for(p;p <= n;p += p&-p)
      |         ^
index.cpp: In function 'long long int get(long long int)':
index.cpp:52:9: warning: statement has no effect [-Wunused-value]
   52 |     for(p;p > 0;p -= p&-p)
      |         ^

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