Submission #257939

#	Time	Username	Problem	Language	Result	Execution time	Memory
257939		youngyojun	Employment (JOI16_employment)	C++17	100 / 100	342 ms	10616 KiB

employment

#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
 
const int MAXN = 200005;
const int MAXQ = 200005;
const int MX = 524288;
 
struct BIT {
	int d[MX*2];
	void upd(int x, int r) {
		for(x += MX; x; x /= 2) d[x] += r;
	}
	int get(int s, int e) {
		int r = 0; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
			if(s&1) r += d[s++]; if(~e&1) r += d[e--];
		} return r;
	}
	int get(int x) { return get(x, MX-1); }
} segV, segE;
 
int A[MAXN];
int B[MAXQ], C[MAXQ], D[MAXQ];
 
int N, Q;
 
int main() {
	ios::sync_with_stdio(false);
	
	cin >> N >> Q;
	for(int i = 1; i <= N; i++) cin >> A[i];
	for(int i = 1; i <= Q; i++) {
		cin >> B[i] >> C[i];
		if(2 == B[i]) cin >> D[i];
	}
	
	{
		vector<int> V;
		for(int i = 1; i <= N; i++) V.pb(A[i]);
		for(int i = 1; i <= Q; i++)
			V.pb(1 == B[i] ? C[i] : D[i]);
		
		sorv(V); univ(V);
		
		for(int i = 1; i <= N; i++)
			A[i] = (int)(lower_bound(allv(V), A[i]) - V.begin()) + 1;
		for(int i = 1; i <= Q; i++) {
			if(1 == B[i])
				C[i] = (int)(lower_bound(allv(V), C[i]) - V.begin()) + 1;
			else
				D[i] = (int)(lower_bound(allv(V), D[i]) - V.begin()) + 1;
		}
	}
	
	for(int i = 1; i <= N; i++) {
		segV.upd(A[i], 1);
		if(1 < i && A[i] <= A[i-1]) segE.upd(A[i], 1);
		if(i < N && A[i] < A[i+1]) segE.upd(A[i], 1);
	}
	
	for(int qi = 1; qi <= Q; qi++) {
		if(1 == B[qi]) {
			printf("%d\n", segV.get(C[qi]) - segE.get(C[qi]));
		} else {
			int x = C[qi], y = D[qi];
			{
				segV.upd(A[x], -1);
				if(1 < x && A[x] <= A[x-1]) segE.upd(A[x], -1);
				if(x < N && A[x] < A[x+1]) segE.upd(A[x], -1);
				if(1 < x && A[x-1] < A[x]) segE.upd(A[x-1], -1);
				if(x < N && A[x+1] <= A[x]) segE.upd(A[x+1], -1);
			}
			{
				A[x] = y;
				segV.upd(y, 1);
				if(1 < x && A[x] <= A[x-1]) segE.upd(A[x], 1);
				if(x < N && A[x] < A[x+1]) segE.upd(A[x], 1);
				if(1 < x && A[x-1] < A[x]) segE.upd(A[x-1], 1);
				if(x < N && A[x+1] <= A[x]) segE.upd(A[x+1], 1);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

employment.cpp: In member function 'int BIT::get(int, int)':
employment.cpp:35:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(s&1) r += d[s++]; if(~e&1) r += d[e--];
    ^~
employment.cpp:35:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    if(s&1) r += d[s++]; if(~e&1) r += d[e--];
                         ^~

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