oj.uz

Submission #257945

# Submission time Handle Problem Language Result Execution time Memory
257945 2020-08-05T05:44:00 Z 임성재(#5053) Employment (JOI16_employment) C++17
0 / 100
 2 ms 512 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n, q;
int a[200010];
int t[200010];
int b[200010];
int c[200010];
int tree[201010];
vector<int> v;

void update(int i, int x) {
	while(i <= 200010) {
		tree[i] += x;
		i += i & -i;
	}
}

int sum(int i) {
	int ret = 0;

	while(i) {
		ret += tree[i];

		i -= i & -i;
	}

	return ret;
}

bool up(int x) {
	if(x < 1 || x > n) return false;

	if(a[x-1] < a[x] && a[x] >= a[x+1]) return true;
	return false;
}

bool down(int x) {
	if(x < 1 || x > n) return false;
	if(a[x-1] >= a[x] && a[x] < a[x+1]) return true;
	return false;
}

int main() {
	fast;

	cin >> n >> q;

	for(int i=1; i<=n; i++) {
		cin >> a[i];
		v.eb(a[i]);
	}

	for(int i=1; i<=q; i++) {
		cin >> t[i];

		if(t[i] == 2) cin >> b[i];

		cin >> c[i];

		v.eb(c[i]);
	}

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

	for(int i=1; i<=n; i++) {
		a[i] = lower_bound(all(v), a[i]) - v.begin() + 1;

		if(up(i)) update(a[i]+1, -1);
		if(down(i)) update(a[i]+1, 1);
	}

	for(int i=1; i<=q; i++) {
		c[i] = lower_bound(all(v), c[i]) - v.begin() + 1;

		if(t[i] == 1) {
			cout << sum(c[i]) + 1 << "\n";
		}
		else {
			if(up(b[i])) update(a[b[i]]+1, 1);
			if(down(b[i])) update(a[b[i]]+1, -1);
			if(up(b[i]+1)) update(a[b[i]+1]+1, 1);
			if(down(b[i]+1)) update(a[b[i]+1]+1, -1);
			if(up(b[i]-1)) update(a[b[i]-1]+1, 1);
			if(down(b[i]-1)) update(a[b[i]-1]+1, -1);

			a[b[i]] = c[i];

			if(up(b[i])) update(a[b[i]]+1, -1);
			if(down(b[i])) update(a[b[i]]+1, 1);
			if(up(b[i]+1)) update(a[b[i]+1]+1, -1);
			if(down(b[i]+1)) update(a[b[i]+1]+1, 1);
			if(up(b[i]-1)) update(a[b[i]-1]+1, -1);
			if(down(b[i]-1)) update(a[b[i]-1]+1, 1);
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -