Submission #143525

#	Time	Username	Problem	Language	Result	Execution time	Memory
143525		kig9981	Employment (JOI16_employment)	C++17	100 / 100	250 ms	5828 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];
vector<int> x;
vector<pair<int,int>> Q;

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.push_back(A[i]);
	}
	Q.resize(M);
	for(auto &[a,b]: Q) {
		int t;
		cin>>t>>a; b=-1;
		if(t==2) {
			cin>>b; --a;
			x.push_back(b);
		}
	}
	sort(x.begin(),x.end());
	x.resize(unique(x.begin(),x.end())-x.begin());
	for(int i=0;i<N;i++) A[i]=lower_bound(x.begin(),x.end(),A[i])-x.begin();
	for(int i=0;i<N;i++) set_value(i,1);
	for(auto &[a,b]: Q) {
		if(b==-1) cout<<get_cnt(lower_bound(x.begin(),x.end(),a)-x.begin())<<'\n';
		else {
			set_value(a,-1);
			if(a) set_value(a-1,-1);
			if(a+1<N) set_value(a+1,-1);
			A[a]=lower_bound(x.begin(),x.end(),b)-x.begin();
			set_value(a,1);
			if(a) set_value(a-1,1);
			if(a+1<N) set_value(a+1,1);
		}
	}
	return 0;
}

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