oj.uz

Submission #963433

# Submission time Handle Problem Language Result Execution time Memory
963433 2024-04-15T03:01:35 Z pcc Index (COCI21_index) C++17
110 / 110
 322 ms 47288 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 2e5+10;

struct BIT{
	int bit[mxn];
	void modify(int p,int v){
		for(;p<mxn;p+=p&-p)bit[p] += v;
		return;
	}
	int getval(int s,int e){
		int re = 0;
		for(;e>0;e-= e&-e)re += bit[e];
		s--;
		for(;s>0;s-= s&-s)re -= bit[s];
		return re;
	}
};

struct D{
	int tp,a,b,tag;
	D(){}
	D(int tt,int aa,int bb,int tg = 0):tp(tt),a(aa),b(bb),tag(tg){}
};

int ans[mxn];
int arr[mxn];
int N,Q;
BIT bit;

void dc(int l,int r,vector<D> &v){
	if(v.empty())return;
	if(l == r){
		for(auto &i:v){
			if(i.tp)ans[i.tp] = l;
		}
		return;
	}
	int mid = (l+r)>>1;
	vector<D> lv,rv;
	for(auto &i:v){
		if(!i.tp){
			if(i.b<=mid)lv.push_back(i);
			else{
				rv.push_back(i);
				bit.modify(i.a,1);
			}
		}
		else{
			if(bit.getval(i.a,i.b)+i.tag>mid)rv.push_back(i);
			else{
				i.tag += bit.getval(i.a,i.b);
				lv.push_back(i);
			}
		}
	}
	for(auto &i:rv){
		if(!i.tp)bit.modify(i.a,-bit.getval(i.a,i.a));
	}
	dc(l,mid,lv);
	dc(mid+1,r,rv);
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	vector<D> v;
	for(int i = 1;i<=N;i++){
		int k;
		cin>>k;
		v.push_back(D(0,i,k));
	}
	for(int i = 1;i<=Q;i++){
		int s,e;
		cin>>s>>e;
		v.push_back(D(i,s,e));
	}
	dc(0,mxn-1,v);
	for(int i = 1;i<=Q;i++)cout<<ans[i]<<'\n';
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2904 KB Output is correct
2 Correct 3 ms 2908 KB Output is correct
3 Correct 3 ms 2908 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 2 ms 2904 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 74 ms 15484 KB Output is correct
12 Correct 74 ms 15952 KB Output is correct
13 Correct 78 ms 15828 KB Output is correct
14 Correct 73 ms 15560 KB Output is correct
15 Correct 73 ms 15728 KB Output is correct
16 Correct 78 ms 15812 KB Output is correct
17 Correct 72 ms 15472 KB Output is correct
18 Correct 77 ms 15876 KB Output is correct
19 Correct 77 ms 15824 KB Output is correct
20 Correct 73 ms 15560 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2904 KB Output is correct
2 Correct 3 ms 2908 KB Output is correct
3 Correct 3 ms 2908 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 2 ms 2904 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 74 ms 15484 KB Output is correct
12 Correct 74 ms 15952 KB Output is correct
13 Correct 78 ms 15828 KB Output is correct
14 Correct 73 ms 15560 KB Output is correct
15 Correct 73 ms 15728 KB Output is correct
16 Correct 78 ms 15812 KB Output is correct
17 Correct 72 ms 15472 KB Output is correct
18 Correct 77 ms 15876 KB Output is correct
19 Correct 77 ms 15824 KB Output is correct
20 Correct 73 ms 15560 KB Output is correct
21 Correct 322 ms 45740 KB Output is correct
22 Correct 302 ms 44120 KB Output is correct
23 Correct 308 ms 46960 KB Output is correct
24 Correct 310 ms 44728 KB Output is correct
25 Correct 306 ms 46260 KB Output is correct
26 Correct 301 ms 47288 KB Output is correct
27 Correct 319 ms 44448 KB Output is correct
28 Correct 302 ms 45068 KB Output is correct
29 Correct 305 ms 46264 KB Output is correct
30 Correct 300 ms 47180 KB Output is correct