oj.uz

Submission #53724

# Submission time Handle Problem Language Result Execution time Memory
53724 2018-07-01T05:57:29 Z ainta(#1540) Employment (JOI16_employment) C++11
0 / 100
 6 ms 604 KB 
#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 <= n; 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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Incorrect 4 ms 476 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Incorrect 4 ms 476 KB Output isn't correct
5 Halted 0 ms 0 KB -