oj.uz

Submission #491515

# Submission time Handle Problem Language Result Execution time Memory
491515 2021-12-02T19:03:17 Z kingfran1907 Employment (JOI16_employment) C++14
0 / 100
 2 ms 364 KB 
#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, 1);
			update(niz[i], -1);
		}
	}

	//printf("Debug: ");
	//for (int i = 0; i < n; i++)
	//	printf("%d ", niz[i]);
	//printf("\n");
	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, -1);
				update(niz[x], 1);
			}
			if (niz[x] < niz[x + 1]) {
				update(niz[x] + 1, -1);
				update(niz[x + 1], 1);
			}
			niz[x] = qs[i].Y;

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

Compilation message

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.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 60.0

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