Submission #155895

#	Time	Username	Problem	Language	Result	Execution time	Memory
155895		MetB	Tenis (COI19_tenis)	C++14	100 / 100	251 ms	7248 KiB

tenis

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
 
using namespace std;
 
typedef long long ll;
 
const ll INF = 1e9, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

int n, q, a[1000000][3], m[1000000], c[1000000];

struct SegTree {
	int t[4000000], t_add[4000000], start;

	void push (int node) {
		if (node < start) {
			t_add[2 * node] += t_add[node];
			t_add[2 * node + 1] += t_add[node];
		}
		t[node] += t_add[node];
		t_add[node] = 0;
	}

	void build (int n) {
		start = 1;
		while (start < n) start <<= 1;

		int sum = 0;

		for (int i = 0; i < n; i++) {
			sum += c[i];
			t[i + start] = i + 1 - sum;
		}

		for (int i = start - 1; i; i--)
			t[i] = min (t[2 * i], t[2 * i + 1]);
	}

	void update (int node, int tl, int tr, int l, int r, int d) {
		push (node);

		if (tr < l || r < tl) return;
		if (l <= tl && tr <= r) {
			t_add[node] += d;
			push (node);
			return;
		}

		int tm = (tl + tr) / 2;

		update (2 * node, tl, tm, l, r, d);
		update (2 * node + 1, tm + 1, tr, l, r, d);

		t[node] = min (t[2 * node], t[2 * node + 1]);
	}

	int order_stat (int node, int tl, int tr) {
		push (node);

		if (tl == tr) return tl;

		int tm = (tl + tr) / 2;

		push (2 * node);

		if (t[2 * node] == 0) return order_stat (2 * node, tl, tm);
		else return order_stat (2 * node + 1, tm + 1, tr);
	}
} t;

void update (int x) {
	t.update (1, 0, t.start - 1, m[x], n - 1, 1);
	m[x] = max (a[x][0], max (a[x][1], a[x][2]));
	t.update (1, 0, t.start - 1, m[x], n - 1, -1);
}

int main () {
	cin >> n >> q;
	for (int j = 0; j < 3; j++)
		for (int i = 0; i < n; i++) {
			int x;
			scanf ("%d", &x);
			a[x-1][j] = i;
		}

	for (int i = 0; i < n; i++) {
		m[i] = max (a[i][0], max (a[i][1], a[i][2]));
		c[m[i]]++;
	}

	t.build (n);

	for (int i = 0; i < q; i++) {
		int p, x, y, type;
		scanf ("%d", &type);

		if (type == 2) {
			scanf ("%d%d%d", &p, &x, &y);

			swap (a[x-1][p-1], a[y-1][p-1]);

			update (x - 1);
			update (y - 1);
		}
		else {
			scanf ("%d", &x);

			if (t.order_stat (1, 0, t.start - 1) >= m[x-1]) printf ("DA\n");
			else printf ("NE\n");
		}
	}
}

Compilation message (stderr)

tenis.cpp: In function 'int main()':
tenis.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d", &x);
    ~~~~~~^~~~~~~~~~
tenis.cpp:101:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &type);
   ~~~~~~^~~~~~~~~~~~~
tenis.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d%d%d", &p, &x, &y);
    ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
tenis.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d", &x);
    ~~~~~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 49 / 49