Submission #143500

#	Time	Username	Problem	Language	Result	Execution time	Memory
143500		songc	Employment (JOI16_employment)	C++14	100 / 100	589 ms	14948 KiB

employment

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, Q;
int qu[202020], X[202020], Y[202020];
int A[202020];
int T[1505050];
vector<int> comp;

int com(int x){return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1;}

void update(int id, int s, int e, int ts, int te, int v){
	if (e < ts || te < s) return;
	if (ts <= s && e <= te){
		T[id] += v;
		return;
	}

	int mid = (s+e)/2;
	update(id*2, s, mid, ts, te, v);
	update(id*2+1, mid+1, e, ts, te, v);
}

int query(int id, int s, int e, int t){
	if (e < t || t < s) return 0;
	if (s == e) return T[id];
	int mid = (s+e)/2;
	return query(id*2, s, mid, t) + query(id*2+1, mid+1, e, t) + T[id];
}

int main(){
	scanf("%d %d", &N, &Q);
	for (int i=1; i<=N; i++){
		scanf("%d", &A[i]);
		comp.push_back(A[i]);
	}
	for (int i=1; i<=Q; i++){
		scanf("%d", &qu[i]);
		scanf("%d", &X[i]);
		comp.push_back(X[i]);
		if (qu[i] == 2){
			scanf("%d", &Y[i]);
			comp.push_back(Y[i]);
		}
	}
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	for (int i=1; i<=N; i++) {
		A[i] = com(A[i]);
		update(1, 1, comp.size(), min(A[i], A[i-1])+1, max(A[i], A[i-1]), 1);
	}
	update(1, 1, comp.size(), 1, A[N], 1);
	for (int i=1; i<=Q; i++){
		if (qu[i] == 1) printf("%d\n", query(1, 1, comp.size(), com(X[i])) / 2);
		else {
			update(1, 1, comp.size(), min(A[X[i]], A[X[i]-1])+1, max(A[X[i]], A[X[i]-1]), -1);
			update(1, 1, comp.size(), min(A[X[i]], A[X[i]+1])+1, max(A[X[i]], A[X[i]+1]), -1);
			A[X[i]] = com(Y[i]);
			update(1, 1, comp.size(), min(A[X[i]], A[X[i]-1])+1, max(A[X[i]], A[X[i]-1]), 1);
			update(1, 1, comp.size(), min(A[X[i]], A[X[i]+1])+1, max(A[X[i]], A[X[i]+1]), 1);
		}
	}
	return 0;
}

Compilation message (stderr)

employment.cpp: In function 'int main()':
employment.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
employment.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
   ~~~~~^~~~~~~~~~~~~
employment.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &qu[i]);
   ~~~~~^~~~~~~~~~~~~~
employment.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &X[i]);
   ~~~~~^~~~~~~~~~~~~
employment.cpp:44:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &Y[i]);
    ~~~~~^~~~~~~~~~~~~

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