제출 #1011202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1011202		pcc	Employment (JOI16_employment)	C++17	100 / 100	169 ms	17812 KiB

employment

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second
#define _all(T) T.begin(),T.end()

const int mxn = 2e5+10;
const int LEN = 1e6;

struct BIT{
	int bit[LEN];
	BIT(){
		memset(bit,0,sizeof(bit));
	}
	void modify(int p,int v){
		for(;p<LEN;p+=p&-p)bit[p] += v;
		return;
	}
	int getval(int s,int e = -1){
		if(e==-1)swap(s,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;
	}
};

int arr[mxn];
BIT bit1,bit2;
int N,Q;
vector<int> all;
pii req[mxn];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++){
		cin>>arr[i];
		all.push_back(arr[i]);
	}
	all.push_back(-1);
	for(int i = 1;i<=Q;i++){
		int t;
		cin>>t;
		if(t == 2){
			int a,b;
			cin>>a>>b;
			req[i] = pii(a,b);
			all.push_back(b);
		}
		else{
			int k;
			cin>>k;
			all.push_back(k);
			req[i] = pii(-1,k);
		}
	}
	sort(_all(all));all.resize(unique(_all(all))-all.begin());
	for(int i = 0;i<=N+1;i++){
		arr[i] = lower_bound(_all(all),arr[i])-all.begin();
		bit2.modify(arr[i],1);
	}
	for(int i = 1;i<=N+1;i++){
		bit1.modify(min(arr[i],arr[i-1]),1);
	}
	for(int i = 1;i<=Q;i++){
		req[i].sc = lower_bound(_all(all),req[i].sc)-all.begin();
		if(req[i].fs<0){
			int tar = req[i].sc;
			cout<<bit2.getval(tar,all.size())-bit1.getval(tar,all.size())<<'\n';
		}
		else{
			auto [pos,val] = req[i];
			bit2.modify(arr[pos],-1);
			bit1.modify(min(arr[pos],arr[pos-1]),-1);
			bit1.modify(min(arr[pos],arr[pos+1]),-1);
			arr[pos] = val;
			bit2.modify(arr[pos],1);
			bit1.modify(min(arr[pos],arr[pos-1]),1);
			bit1.modify(min(arr[pos],arr[pos+1]),1);
		}
	}
	return 0;
}

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