oj.uz

Submission #574507

# Submission time Handle Problem Language Result Execution time Memory
574507 2022-06-08T16:08:43 Z jcelin Index (COCI21_index) C++14
110 / 110
 296 ms 27844 KB 
#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;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define ii pair<ll,ll>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vLL>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 7;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;

int L[MAXN], R[MAXN];
int ans[MAXN];
int n, q;

vi val[MAXN];


int fenw[MAXN];

void update(int x, int val){
	for(; x < MAXN; x += (x & -x)) fenw[x] += val;
}

int query(int x){
	int ret = 0;
	for(; x; x-= (x & -x)) ret += fenw[x];
	return ret;
}


void rek(int lo, int hi, vi a){
	if(a.empty()) return;
	if(lo > hi) return;
	
	if(lo == hi){
		for(auto &x : val[lo]) update(x, 1);
		for(auto &x : a){
			int lef = L[x], rig = R[x];
			if(query(rig) - query(lef - 1) >= lo) ans[x] = lo;
		}
		for(auto &x : val[lo]) update(x, -1);
		return;
	}
	
	int mid = (lo + hi) / 2;
	for(int i=mid; i<=hi; i++) for(auto &x: val[i]) update(x, 1);
	
	
	vi lef, rig;
	for(auto &x : a){
		int le = L[x], ri = R[x];
		if(query(ri) - query(le - 1) >= mid) ans[x] = mid, rig.PB(x);
		else lef.PB(x);
	}
	a.clear();
	rek(lo, mid-1, lef);
	for(int i=mid; i<=hi; i++) for(auto &x: val[i]) update(x, -1);
	rek(mid + 1, hi, rig);
}

void solve(){
	cin >> n >> q;
	for(int i=1, x; i<=n; i++) cin >> x, val[x].PB(i);
	vi a;
	for(int i=1; i<=q; i++) cin >> L[i] >> R[i], a.PB(i);
	rek(1, 200000, a);
	for(int i=1; i<=q; i++) cout << ans[i] << "\n";
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
	//cin >> t;
	while(t--)solve();
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5164 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 5 ms 5164 KB Output is correct
6 Correct 5 ms 5204 KB Output is correct
7 Correct 4 ms 5148 KB Output is correct
8 Correct 5 ms 5204 KB Output is correct
9 Correct 4 ms 5164 KB Output is correct
10 Correct 4 ms 5168 KB Output is correct
11 Correct 60 ms 11364 KB Output is correct
12 Correct 64 ms 11300 KB Output is correct
13 Correct 61 ms 11256 KB Output is correct
14 Correct 66 ms 11420 KB Output is correct
15 Correct 63 ms 11400 KB Output is correct
16 Correct 60 ms 11328 KB Output is correct
17 Correct 59 ms 11396 KB Output is correct
18 Correct 63 ms 11424 KB Output is correct
19 Correct 68 ms 11376 KB Output is correct
20 Correct 61 ms 11384 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5164 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 5 ms 5164 KB Output is correct
6 Correct 5 ms 5204 KB Output is correct
7 Correct 4 ms 5148 KB Output is correct
8 Correct 5 ms 5204 KB Output is correct
9 Correct 4 ms 5164 KB Output is correct
10 Correct 4 ms 5168 KB Output is correct
11 Correct 60 ms 11364 KB Output is correct
12 Correct 64 ms 11300 KB Output is correct
13 Correct 61 ms 11256 KB Output is correct
14 Correct 66 ms 11420 KB Output is correct
15 Correct 63 ms 11400 KB Output is correct
16 Correct 60 ms 11328 KB Output is correct
17 Correct 59 ms 11396 KB Output is correct
18 Correct 63 ms 11424 KB Output is correct
19 Correct 68 ms 11376 KB Output is correct
20 Correct 61 ms 11384 KB Output is correct
21 Correct 275 ms 27736 KB Output is correct
22 Correct 264 ms 27676 KB Output is correct
23 Correct 281 ms 27668 KB Output is correct
24 Correct 271 ms 27504 KB Output is correct
25 Correct 286 ms 27700 KB Output is correct
26 Correct 262 ms 27464 KB Output is correct
27 Correct 267 ms 27424 KB Output is correct
28 Correct 296 ms 27844 KB Output is correct
29 Correct 263 ms 27328 KB Output is correct
30 Correct 276 ms 27512 KB Output is correct