Submission #157052

#	Time	Username	Problem	Language	Result	Execution time	Memory
157052		jhwest2	Employment (JOI16_employment)	C++14	30 / 100	689 ms	34176 KiB

employment

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

struct Query{
	int t, a, b;
} Q[202020];
int N, M;
int A[202020];
vector<int> v;

struct SEG {
	vector<ll> tree, lazy;

	void init(int n) {
		tree.resize(4*n), lazy.resize(4*n);
	}

	void lpush(int lo, int hi, int idx) {
		if (lazy[idx] == 0) return;
		tree[idx] += (hi-lo+1)*lazy[idx];

		if (lo==hi) { lazy[idx] = 0; return; }
		lazy[2*idx] += lazy[idx];
		lazy[2*idx+1] += lazy[idx];
		lazy[idx] = 0; return;
	}

	ll update(int a, int b, int x, int lo, int hi, int idx) {
		lpush(lo, hi, idx);
		if (b<lo || a>hi) return tree[idx];
		if (a<=lo && hi<=b) {
			lazy[idx] += x; lpush(lo, hi, idx);
			return tree[idx];
		}
		return tree[idx] = update(a, b, x, lo, lo+hi>>1, 2*idx) + update(a, b, x, 1+(lo+hi>>1), hi, 2*idx+1);
	}

	ll query(int a, int b, int lo, int hi, int idx) {
		lpush(lo, hi, idx);
		if (b<lo || a>hi) return 0;
		if (a<=lo && hi<=b) return tree[idx];

		return query(a, b, lo, lo+hi>>1, 2*idx) + query(a, b, 1+(lo+hi>>1), hi, 2*idx+1);
	}
} seg;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin >> N >> M;
	for (int i=0; i<N; i++) { cin >> A[i]; v.push_back(A[i]); }

	for (int i=0; i<M; i++) {
		cin >> Q[i].t;
		if (Q[i].t == 1) { cin >> Q[i].a; v.push_back(Q[i].a); }
		else { cin >> Q[i].a >> Q[i].b; v.push_back(Q[i].b); }
	}

	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	for (int i=0; i<N; i++)
		A[i] = lower_bound(v.begin(), v.end(), A[i])-v.begin();

	for (int i=0; i<M; i++) {
		if (Q[i].t==1) Q[i].a = lower_bound(v.begin(), v.end(), Q[i].a)-v.begin();
		else Q[i].b = lower_bound(v.begin(), v.end(), Q[i].b)-v.begin();
	}

	seg.init(v.size());

	seg.update(0, A[0], 1, 0, v.size(), 1);
	for (int i=1; i<N; i++) {
		if (A[i-1] < A[i]) seg.update(A[i-1]+1, A[i], 1, 0, v.size(), 1);
	}

	for (int i=0; i<M; i++) {
		if (Q[i].t == 1) cout << seg.query(Q[i].a, Q[i].a, 0, v.size(), 1) << '\n';
		else {
			int l, h;
			l = min(A[max(0, Q[i].a-2)], A[min((int)v.size()-1, Q[i].a)]);
			h = max(A[max(0, Q[i].a-2)], A[min((int)v.size()-1, Q[i].a)]);

			if (A[Q[i].a] < Q[i].b) {
				seg.update(A[Q[i].a-1]+1, l, -1, 0, v.size(), 1);
				seg.update(h+1, Q[i].b, 1, 0, v.size(), 1);
				A[Q[i].a-1] = Q[i].b;
			}
			else {
				seg.update(Q[i].b+1, l, 1, 0, v.size(), 1);
				seg.update(h+1, A[Q[i].a-1], -1, 0, v.size(), 1);
				A[Q[i].a-1] = Q[i].b;
			}
		}
	}
}

Compilation message (stderr)

employment.cpp: In member function 'll SEG::update(int, int, int, int, int, int)':
employment.cpp:40:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return tree[idx] = update(a, b, x, lo, lo+hi>>1, 2*idx) + update(a, b, x, 1+(lo+hi>>1), hi, 2*idx+1);
                                          ~~^~~
employment.cpp:40:82: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return tree[idx] = update(a, b, x, lo, lo+hi>>1, 2*idx) + update(a, b, x, 1+(lo+hi>>1), hi, 2*idx+1);
                                                                                ~~^~~
employment.cpp: In member function 'll SEG::query(int, int, int, int, int)':
employment.cpp:48:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return query(a, b, lo, lo+hi>>1, 2*idx) + query(a, b, 1+(lo+hi>>1), hi, 2*idx+1);
                          ~~^~~
employment.cpp:48:62: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return query(a, b, lo, lo+hi>>1, 2*idx) + query(a, b, 1+(lo+hi>>1), hi, 2*idx+1);
                                                            ~~^~~

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