Submission #143526

#	Time	Username	Problem	Language	Result	Execution time	Memory
143526		kig9981	Employment (JOI16_employment)	C++17	100 / 100	234 ms	5636 KiB

employment

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

int N, tree[400001], A[200000], x[400000], sz;
pair<int,int> Q[200000];

void update(int n, int v)
{
	for(++n;n;n-=n&-n) tree[n]+=v;
}

int get_cnt(int n)
{
	int ret=0;
	for(++n;n<=400000;n+=n&-n) ret+=tree[n];
	return ret;
}

void set_value(int i, int m)
{
	int v=i==0;
	v+=(i && A[i-1]<A[i]);
	v-=(i+1<N && A[i]<A[i+1]);
	update(A[i],m*v);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt", "r", stdin));
	TEST(freopen("output.txt", "w", stdout));
	TEST(freopen("debug.txt", "w", stderr));
	int M;
	cin>>N>>M;
	for(int i=0;i<N;i++) {
		cin>>A[i];
		x[sz++]=A[i];
	}
	for(int i=0;i<M;i++) {
		int t;
		cin>>t>>Q[i].first; Q[i].second=-1;
		if(t==2) {
			cin>>Q[i].second; --Q[i].first;
			x[sz++]=Q[i].second;
		}
	}
	sort(x,x+sz);
	sz=unique(x,x+sz)-x;
	for(int i=0;i<N;i++) A[i]=lower_bound(x,x+sz,A[i])-x;
	for(int i=0;i<N;i++) set_value(i,1);
	for(int i=0;i<M;i++) {
		if(Q[i].second==-1) cout<<get_cnt(lower_bound(x,x+sz,Q[i].first)-x)<<'\n';
		else {
			set_value(Q[i].first,-1);
			if(Q[i].first) set_value(Q[i].first-1,-1);
			if(Q[i].first+1<N) set_value(Q[i].first+1,-1);
			A[Q[i].first]=lower_bound(x,x+sz,Q[i].second)-x;
			set_value(Q[i].first,1);
			if(Q[i].first) set_value(Q[i].first-1,1);
			if(Q[i].first+1<N) set_value(Q[i].first+1,1);
		}
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60