Submission #105714

#	Time	Username	Problem	Language	Result	Execution time	Memory
105714		Pro_ktmr	Employment (JOI16_employment)	C++14	100 / 100	1018 ms	22580 KiB

employment

#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 (stderr)

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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60