oj.uz

Submission #105714

# Submission time Handle Problem Language Result Execution time Memory
105714 2019-04-14T04:21:18 Z Pro_ktmr Employment (JOI16_employment) C++14
100 / 100
 1018 ms 22580 KB 
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define MP(a,b) make_pair(a,b)

struct SegmentTree{
private:
	int N;
	vector<int> node,lazy;
public:
	void init(int n){
		N = 1;
		while(N < n) N *= 2;
		N = 2*N-1;
		node.clear();
		lazy.clear();
		for(int i=0; i<N; i++) node.push_back(0);
		for(int i=0; i<N; i++) lazy.push_back(0);
	}
	void eval(int k, int l, int r){
		if(lazy[k] == 0) return;
		node[k] += (r-l)*lazy[k];
		if(r-l != 1){
			lazy[2*k+1] += lazy[k];
			lazy[2*k+2] += lazy[k];
		}
		lazy[k] = 0;
	}
	void update(int a, int b, int x, int k=0, int l=0, int r=-1){
		if(r == -1) r = (N+1) / 2;
		eval(k, l, r);
		if(r <= a || b <= l) return;
		if(a <= l && r <= b){
			lazy[k] += x;
			eval(k, l, r);
		}
		else{
			update(a, b, x, 2*k+1, l, (l+r)/2);
			update(a, b, x, 2*k+2, (l+r)/2, r);
			node[k] = node[2*k+1] + node[2*k+2];
		}
	}
	int find(int a, int k=0, int l=0, int r=-1){
		if(r == -1) r = (N+1) / 2;
		eval(k, l, r);
		if(r-l == 1) return node[k];
		if(a < (l+r)/2) return find(a, 2*k+1, l, (l+r)/2);
		else return find(a, 2*k+2, (l+r)/2, r);
	}
	void print(){
		for(int k=0; k<N/2; k++){
			node[k] += lazy[k];
			lazy[2*k+1] += lazy[k];
			lazy[2*k+2] += lazy[k];
			lazy[k] = 0;
		}
		for(int k=N/2; k<N; k++){
			node[k] += lazy[k];
			lazy[k] = 0;
			cout << node[k] << " ";
		}
		cout << endl;
	}
};

int N,Q;
int A[200000];
int T[200000],X[200000],P[200000];
vector<int> z;
SegmentTree st;

int main(){
	cin >> N >> Q;
	for(int i=0; i<N; i++){
		cin >> A[i];
		z.push_back(A[i]);
	}
	for(int i=0; i<Q; i++){
		cin >> T[i];
		if(T[i] == 1) cin >> X[i];
		else{
			cin >> P[i] >> X[i];
			P[i]--;
		}
		z.push_back(X[i]);
	}
	z.push_back(-1);
	sort(z.begin(), z.end());
	for(int i=0; i<N; i++){
		A[i] = lower_bound(z.begin(), z.end(), A[i]) - z.begin();
	}
	for(int i=0; i<Q; i++){
		X[i] = lower_bound(z.begin(), z.end(), X[i]) - z.begin();
	}
	
	//
	
	st.init(z.size());
	vector<pair<int,int> > v;
	for(int i=0; i<N; i++){
		v.push_back(MP(A[i], i));
	}
	sort(v.begin(), v.end());
	int now = 0;
	int tmp = 1;
	for(int i=0; i<z.size(); i++){
		while(now < N && v[now].first < i){
			if(v[now].second == 0){
				if(A[v[now].second+1] < v[now].first) tmp--;
			}
			else if(v[now].second == N-1){
				if(A[v[now].second-1] <= v[now].first) tmp--;
			}
			else{
				if(A[v[now].second-1] <= v[now].first && A[v[now].second+1] < v[now].first) tmp--;
				else if(A[v[now].second-1] > v[now].first && A[v[now].second+1] >= v[now].first) tmp++;
			}
			now++;
		}
		st.update(i, i+1, tmp);
	}
	//st.print();
	
	//
	
	for(int i=0; i<Q; i++){
		if(T[i] == 2){
			if(X[i] < A[P[i]]){
				vector<int> t;
				t.push_back(X[i]);
				t.push_back(A[P[i]]);
				if(P[i] != 0) t.push_back(A[P[i]-1]);
				if(P[i] != N-1) t.push_back(A[P[i]+1]);
				sort(t.begin(), t.end());
				reverse(t.begin(), t.end());
				if(A[P[i]] >= t[0] && t[1] >= X[i]) st.update(t[1]+1, t[0]+1, -1);
				if(t.size() == 4 && A[P[i]] >= t[2] && t[3] >= X[i]) st.update(t[3]+1, t[2]+1, 1);
			}
			if(X[i] > A[P[i]]){
				vector<int> t;
				t.push_back(X[i]);
				t.push_back(A[P[i]]);
				if(P[i] != 0) t.push_back(A[P[i]-1]);
				if(P[i] != N-1) t.push_back(A[P[i]+1]);
				sort(t.begin(), t.end());
				reverse(t.begin(), t.end());
				if(X[i] >= t[0] && t[1] >= A[P[i]]) st.update(t[1]+1, t[0]+1, 1);
				if(t.size() == 4 && X[i] >= t[2] && t[3] >= A[P[i]]) st.update(t[3]+1, t[2]+1, -1);
			}
			A[P[i]] = X[i];
			//st.print();
		}
		else{
			cout << st.find(X[i]) << endl;
		}
	}
	
	return 0;
}

Compilation message

employment.cpp: In function 'int main()':
employment.cpp:106:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<z.size(); i++){
               ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 9 ms 512 KB Output is correct
10 Correct 9 ms 512 KB Output is correct
11 Correct 12 ms 512 KB Output is correct
12 Correct 8 ms 512 KB Output is correct
13 Correct 13 ms 512 KB Output is correct
14 Correct 8 ms 512 KB Output is correct
15 Correct 9 ms 512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 14 ms 768 KB Output is correct
3 Correct 13 ms 640 KB Output is correct
4 Correct 70 ms 1908 KB Output is correct
5 Correct 107 ms 3568 KB Output is correct
6 Correct 189 ms 5616 KB Output is correct
7 Correct 308 ms 9612 KB Output is correct
8 Correct 420 ms 10620 KB Output is correct
9 Correct 772 ms 18180 KB Output is correct
10 Correct 574 ms 18388 KB Output is correct
11 Correct 818 ms 20564 KB Output is correct
12 Correct 810 ms 21460 KB Output is correct
13 Correct 839 ms 21504 KB Output is correct
14 Correct 938 ms 21468 KB Output is correct
15 Correct 893 ms 21544 KB Output is correct
16 Correct 930 ms 21688 KB Output is correct
17 Correct 762 ms 21688 KB Output is correct
18 Correct 863 ms 21500 KB Output is correct
19 Correct 852 ms 21580 KB Output is correct
20 Correct 863 ms 21676 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 9 ms 512 KB Output is correct
10 Correct 9 ms 512 KB Output is correct
11 Correct 12 ms 512 KB Output is correct
12 Correct 8 ms 512 KB Output is correct
13 Correct 13 ms 512 KB Output is correct
14 Correct 8 ms 512 KB Output is correct
15 Correct 9 ms 512 KB Output is correct
16 Correct 9 ms 640 KB Output is correct
17 Correct 14 ms 768 KB Output is correct
18 Correct 13 ms 640 KB Output is correct
19 Correct 70 ms 1908 KB Output is correct
20 Correct 107 ms 3568 KB Output is correct
21 Correct 189 ms 5616 KB Output is correct
22 Correct 308 ms 9612 KB Output is correct
23 Correct 420 ms 10620 KB Output is correct
24 Correct 772 ms 18180 KB Output is correct
25 Correct 574 ms 18388 KB Output is correct
26 Correct 818 ms 20564 KB Output is correct
27 Correct 810 ms 21460 KB Output is correct
28 Correct 839 ms 21504 KB Output is correct
29 Correct 938 ms 21468 KB Output is correct
30 Correct 893 ms 21544 KB Output is correct
31 Correct 930 ms 21688 KB Output is correct
32 Correct 762 ms 21688 KB Output is correct
33 Correct 863 ms 21500 KB Output is correct
34 Correct 852 ms 21580 KB Output is correct
35 Correct 863 ms 21676 KB Output is correct
36 Correct 7 ms 620 KB Output is correct
37 Correct 9 ms 768 KB Output is correct
38 Correct 11 ms 640 KB Output is correct
39 Correct 49 ms 2024 KB Output is correct
40 Correct 114 ms 3428 KB Output is correct
41 Correct 231 ms 5780 KB Output is correct
42 Correct 272 ms 9484 KB Output is correct
43 Correct 350 ms 10904 KB Output is correct
44 Correct 732 ms 20288 KB Output is correct
45 Correct 576 ms 18524 KB Output is correct
46 Correct 690 ms 19512 KB Output is correct
47 Correct 931 ms 22080 KB Output is correct
48 Correct 925 ms 22300 KB Output is correct
49 Correct 958 ms 22272 KB Output is correct
50 Correct 991 ms 22100 KB Output is correct
51 Correct 907 ms 22408 KB Output is correct
52 Correct 892 ms 22388 KB Output is correct
53 Correct 1018 ms 22340 KB Output is correct
54 Correct 912 ms 22376 KB Output is correct
55 Correct 984 ms 22580 KB Output is correct