Submission #491513

#	Time	Username	Problem	Language	Result	Execution time	Memory
491513		kingfran1907	Employment (JOI16_employment)	C++14	0 / 100	1 ms	332 KiB

employment

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 1e6+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, q;
int niz[maxn];
int loga[maxn];
vector< int > v;
pair< int, int > qs[maxn];

void update(int x, int val) {
	for (x++; x < maxn; x += x & -x)
		loga[x] += val;
}

int query(int x) {
	int out = 0;
	for (x++; x > 0; x -= x & -x)
		out += loga[x];
	return out;
}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++)
		scanf("%d", niz+i);

	for (int i = 0; i <= n; i++)
		v.push_back(niz[i]);
	for (int i = 0; i < q; i++) {
		int type;
		scanf("%d", &type);
		if (type == 1) {
			int x;
			scanf("%d", &x);
			qs[i] = make_pair(-1, x);
		} else {
			int x, y;
			scanf("%d%d", &x, &y);

			qs[i] = make_pair(x, y);
			//v.push_back(y);
		}
		v.push_back(qs[i].Y);
	}

	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	for (int i = 0; i <= n; i++)
		niz[i] = lower_bound(v.begin(), v.end(), niz[i]) - v.begin();
	for (int i = 0; i < q; i++) {
		qs[i].Y = lower_bound(v.begin(), v.end(), qs[i].Y) - v.begin();
	}

	for (int i = 1; i <= n; i++) {
		if (niz[i - 1] < niz[i]) {
			update(niz[i - 1], 1);
			update(niz[i] + 1, 1);
		}
	}

	for (int i = 0; i < q; i++) {
		if (qs[i].X == -1) {
			printf("%d\n", query(qs[i].Y));
		} else {
			int x = qs[i].X;
			if (niz[x - 1] < niz[x]) {
				update(niz[x - 1], -1);
				update(niz[x] + 1, 1);
			}
			if (niz[x] < niz[x + 1]) {
				update(niz[x], -1);
				update(niz[x + 1] + 1, 1);
			}
			niz[x] = qs[i].Y;

			if (niz[x - 1] < niz[x]) {
				update(niz[x - 1], 1);
				update(niz[x] + 1, -1);
			}
			if (niz[x] < niz[x + 1]) {
				update(niz[x], 1);
				update(niz[x + 1] + 1, -1);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

employment.cpp: In function 'int main()':
employment.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
employment.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%d", niz+i);
      |   ~~~~~^~~~~~~~~~~~~
employment.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d", &type);
      |   ~~~~~^~~~~~~~~~~~~
employment.cpp:46:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~
employment.cpp:50:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |    scanf("%d%d", &x, &y);
      |    ~~~~~^~~~~~~~~~~~~~~~

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