Submission #53852

#	Time	Username	Problem	Language	Result	Execution time	Memory
53852		ainta	Employment (JOI16_employment)	C++17	100 / 100	355 ms	6904 KiB

employment

#include<cstdio>
#include<algorithm>
#define SZ 401000
using namespace std;
int n, m;
int w[SZ];
int X[SZ], BIT[SZ], CX;
struct Query {
	int a, b, c;
}Q[SZ];
void Add(int a, int b) {
	while (a <= CX + 1) {
		BIT[a] += b;
		a += (a&-a);
	}
}
int Sum(int a) {
	int r = 0;
	while (a) {
		r += BIT[a];
		a -= (a&-a);
	}
	return r;
}
void Go(int a, int b) {
	if (a <= n && w[a - 1] <= w[a]) {
		Add(w[a - 1] + 1, b);
		Add(w[a] + 1, -b);
	}
}
int main() {
	int i, a, b, c;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		X[++CX] = w[i];
	}
	for (i = 1; i <= m; i++) {
		scanf("%d%d", &Q[i].c, &Q[i].a);
		Q[i].b = 0;
		if (Q[i].c == 2) {
			scanf("%d", &Q[i].b);
			X[++CX] = Q[i].b;
		}
	}
	sort(X + 1, X + CX + 1);
	for (i = 1; i <= n; i++) {
		w[i] = lower_bound(X + 1, X + CX + 1, w[i]) - X;
		Go(i, 1);
	}
	for (i = 1; i <= m; i++) {
		a = Q[i].a, b = Q[i].b, c = Q[i].c;
		if (c == 1) {
			a = lower_bound(X + 1, X + CX + 1, a) - X;
			printf("%d\n", Sum(a));
		}
		else {
			b = lower_bound(X + 1, X + CX + 1, b) - X;
			Go(a, -1);
			Go(a + 1, -1);
			w[a] = b;
			Go(a, 1);
			Go(a + 1, 1);
		}
	}
}

Compilation message (stderr)

employment.cpp: In function 'int main()':
employment.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
employment.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i]);
   ~~~~~^~~~~~~~~~~~~
employment.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &Q[i].c, &Q[i].a);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
employment.cpp:42:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &Q[i].b);
    ~~~~~^~~~~~~~~~~~~~~

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