Submission #189405

#	Time	Username	Problem	Language	Result	Execution time	Memory
189405		dndhk	Employment (JOI16_employment)	C++14	100 / 100	1322 ms	41244 KiB

employment

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 200000;

int N, M, K;
int A[MAX_N+1];
vector<int> vt;
struct S{
	int t, a, b;
};
vector<S> query;
map<int, int> mp;

void input(){
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++){
		scanf("%d", &A[i]);
		vt.pb(A[i]);
	}
	for(int i=1; i<=M; i++){
		int t, a, b=0;
		scanf("%d", &t);
		if(t==1){
			scanf("%d", &a);
			vt.pb(a);
		}else{
			scanf("%d%d", &a, &b);
			vt.pb(b);
		}
		query.pb({t, a, b});
	}
	sort(vt.begin(), vt.end());
	vt.erase(unique(vt.begin(), vt.end()), vt.end());
	for(int i=0; i<vt.size(); i++){
		mp[vt[i]] = i+1;
	}
	for(int i=1; i<=N; i++)	A[i] = mp[A[i]];
	for(int i=0; i<query.size(); i++){
		if(query[i].t==1){
			query[i].a = mp[query[i].a];
		}else{
			query[i].b = mp[query[i].b];
		}
	}
	K = vt.size();}

struct SEG{
	struct NODE{
		int l, r;
		int sum;
	};
	int SZ;
	vector<NODE> seg;
	void add(){
		seg.pb({-1, -1, 0});
	}
	void Init(int x){
		SZ = x;
		add();
		init(0, 1, SZ);
	}
	void init(int idx, int s, int e){
		if(s==e)	return;
		seg[idx].l = seg.size(); add();
		seg[idx].r = seg.size(); add();
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
	}
	void Add(int x, int y, int z){
		add(0, 1, SZ, x, y, z);
	}
	void add(int idx, int s, int e, int x, int y, int z){
		if(x<=s && e<=y){
			seg[idx].sum+=z;
			return;
		}
		if(x>e || y<s)	return;
		add(seg[idx].l, s, (s+e)/2, x, y, z);
		add(seg[idx].r, (s+e)/2+1, e, x, y, z);
	}
	int Sum(int x){
		return sum(0, 1, SZ, x);
	}
	int sum(int idx, int s, int e, int k){
		if(s==e)	return seg[idx].sum;
		if(k<=(s+e)/2){
			return seg[idx].sum+sum(seg[idx].l, s, (s+e)/2, k);
		}else{
			return seg[idx].sum+sum(seg[idx].r, (s+e)/2+1, e, k);
		}
	}
}Seg;



void add(int x, int y){
	if(N==1){
		Seg.Add(1, y, 1);
		return;
	}
	if(x==1){
		if((pii){y, x} > (pii){A[x+1], x+1}){
			Seg.Add(1, y, 1);
		}
	}else if(x==N){
		if((pii){y, x} > (pii){A[x-1], x-1}){
			Seg.Add(1, y, 1);
		}
	}else{
		if((pii){y, x} > (pii){A[x-1], x-1} && (pii){y, x} > (pii){A[x+1], x+1}){
			Seg.Add(1, y, 1);
		}else if((pii){y, x} < (pii){A[x-1], x-1} && (pii){y, x} < (pii){A[x+1], x+1}){
			Seg.Add(1, y, -1);
		}
	}
}

void rmv(int x, int y){
	if(N==1){
		Seg.Add(1, y, -1);
		return;
	}
	if(x==1){
		if((pii){y, x} > (pii){A[x+1], x+1}){
			Seg.Add(1, y, -1);
		}
	}else if(x==N){
		if((pii){y, x} > (pii){A[x-1], x-1}){
			Seg.Add(1, y, -1);
		}
	}else{
		if((pii){y, x} > (pii){A[x-1], x-1} && (pii){y, x} > (pii){A[x+1], x+1}){
			Seg.Add(1, y, -1);
		}else if((pii){y, x} < (pii){A[x-1], x-1} && (pii){y, x} < (pii){A[x+1], x+1}){
			Seg.Add(1, y, 1);
		}
	}
}

int main(){
	input();
	Seg.Init(K);
	for(int i=1; i<=N; i++){
		add(i, A[i]);
	}
	for(int i=0; i<query.size(); i++){
		int t = query[i].t, a = query[i].a, b = query[i].b;
		if(t==2){
			rmv(a, A[a]);
			if(a!=1){
				rmv(a-1, A[a-1]);
			}if(a!=N){
				rmv(a+1, A[a+1]);
			}
			A[a] = b;
			add(a, b);
			if(a!=1){
				add(a-1, A[a-1]);
			}if(a!=N){
				add(a+1, A[a+1]);
			}
		}else{
			printf("%d\n", Seg.Sum(a));
		}
	}
	return 0;
}

Compilation message (stderr)

employment.cpp: In function 'void input()':
employment.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
employment.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<query.size(); i++){
               ~^~~~~~~~~~~~~
employment.cpp: In function 'int main()':
employment.cpp:153:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<query.size(); i++){
               ~^~~~~~~~~~~~~
employment.cpp: In function 'void input()':
employment.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
employment.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
   ~~~~~^~~~~~~~~~~~~
employment.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
employment.cpp:31:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~
employment.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &a, &b);
    ~~~~~^~~~~~~~~~~~~~~~

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