oj.uz

Submission #392125

# Submission time Handle Problem Language Result Execution time Memory
392125 2021-04-20T14:20:24 Z soroush Index (COCI21_index) C++17
110 / 110
 1260 ms 9936 KB 
//*
//#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 287 ms 2568 KB Output is correct
12 Correct 297 ms 2568 KB Output is correct
13 Correct 282 ms 2576 KB Output is correct
14 Correct 285 ms 2628 KB Output is correct
15 Correct 290 ms 2576 KB Output is correct
16 Correct 288 ms 2524 KB Output is correct
17 Correct 284 ms 2580 KB Output is correct
18 Correct 287 ms 2660 KB Output is correct
19 Correct 286 ms 2568 KB Output is correct
20 Correct 284 ms 2628 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 287 ms 2568 KB Output is correct
12 Correct 297 ms 2568 KB Output is correct
13 Correct 282 ms 2576 KB Output is correct
14 Correct 285 ms 2628 KB Output is correct
15 Correct 290 ms 2576 KB Output is correct
16 Correct 288 ms 2524 KB Output is correct
17 Correct 284 ms 2580 KB Output is correct
18 Correct 287 ms 2660 KB Output is correct
19 Correct 286 ms 2568 KB Output is correct
20 Correct 284 ms 2628 KB Output is correct
21 Correct 1239 ms 9844 KB Output is correct
22 Correct 1260 ms 9848 KB Output is correct
23 Correct 1249 ms 9936 KB Output is correct
24 Correct 1234 ms 9844 KB Output is correct
25 Correct 1231 ms 9924 KB Output is correct
26 Correct 1226 ms 9924 KB Output is correct
27 Correct 1248 ms 9796 KB Output is correct
28 Correct 1220 ms 9848 KB Output is correct
29 Correct 1228 ms 9848 KB Output is correct
30 Correct 1226 ms 9852 KB Output is correct