Submission #392125

#	Time	Username	Problem	Language	Result	Execution time	Memory
392125		soroush	Index (COCI21_index)	C++17	110 / 110	1260 ms	9936 KiB

index

//*
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,fma")
//*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 100;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

const int sq = 447;

int n , t;
int a[maxn];
int ans[maxn];
struct query{
	int l , r, ind;
	friend bool operator < (query &a, query &b){
		if(a.l / sq == b.l / sq)return(((a.l / sq)%2) ? (a.r > b.r) : (a.r < b.r));
		return(a.l < b.l);
	}
}q[maxn];

int fen[maxn];

void add(int pos , int x){
	for(; pos ; pos -= pos & -pos)fen[pos] += x;
}

int get(int pos){
	int res = 0;
	for( ; pos < maxn ; pos += pos & -pos)res += fen[pos];
	return(res);
}

int32_t main(){
	migmig;
	cin >> n >> t;
	for(int i = 1 ; i <= n ; i ++)
		cin >> a[i];
	for(int i = 1 ; i <= t ; i ++)
		cin >> q[i].l >> q[i].r , q[i].ind = i;
	sort(q + 1 , q + t + 1);
	int l = 1 , r = 1 , res = 1;
	add(a[1] , 1);
	for(int i = 1 ; i <= t ; i ++){
		while(r < q[i].r){
			r++;
			add(a[r] , 1);
			if(get(res + 1) > res)res++;
		}
		while(l < q[i].l){
			add(a[l] , -1);
			if(get(res) < res)res--;
			l++;
		}
		while(l > q[i].l){
			l--;
			add(a[l] , 1);
			if(get(res+1) > res)res++;
		}
		while(r > q[i].r){
			add(a[r] , -1);
			if(get(res) < res)res--;
			r--;
		}
		ans[q[i].ind] = res;
	}
	for(int i = 1 ; i <= t ; i ++)
		cout << ans[i] << endl;
	return(0);
}

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